General Information
| Student: | Marina Knittel |
|---|---|
| Office: | CoRE 448 |
| School: | Harvey Mudd College |
| E-mail: | mknittel@g.hmc.edu |
| Project: | The Minimum Circuit Size Problem: A possible NP-Intermediate Problem |
Project Description
The Minimum Circuit Size Problem (MCSP) is a computational problem in NP that is widely believed to be hard to compute, although many researchers suspect that it is NOT NP-complete. However, there is currently only weak evidence to support this suspicion. This REU project will endeavor to find stronger evidence, of the form "If MCSP is NP-complete, then something weird happens". Another possible direction involves clarifying the relative complexity of MCSP and other candidate NP-Intermediate problems. The PI has recently proved some new lower bounds on the complexity of MCSP and related problems, and it should be possible to build on this recent progress. The PI has previously supervised research with REU students on this topic which has led to publications, and there is more work to be done, which should be accessible to an REU student.
Weekly Log
- Week 1:
- Previous to this week, I had been in contact with my mentor, Professor Eric Allender. We had discussed what we want to get out of the REU, and he provided me with a few articles to familiarzie myself with MCSP, related problems, and possible open questions in the area. This week, we met in person to discuss more specific goals for the research itself. We agreed to start out by exploring the Gap problem for Kolmogorov random strings. He had previously theorized that this problem could be reduced to all problems in BPP and vice versa using polynomial time Turing reductions. My first step will be to try to find a truth-table reduction from BPP to the Gap problem in question. I will attempt to base this proof off the known proof of a polynomial truth table reduction from BPP to Kolmogorov random strings. In addition, I managed to complete my first presentation and create my personal website this week.
- Week 2:
- Through most of Monday morning, the REU students gave and listened to all the initial project presentations. After that, Professor Allender and I discussed more about how we were going to approach solving the problem. We wanted to make sure a proof of a less restrictive reduction from BPP to R (the set of Kolmogorov random strings) applied to the gap problem as well, and I verified this worked if we tweaked the assumption slightly. After that, I began trying to work towards a more restrictive reduction. So far, I have not achieved any results. I have begun to break the problem down by trying to find various qualities of the initial conditions of the problem. We'll see where that takes me next week.
- Week 3:
- This week I attempted to break the problem down into smaller pieces to see if I could find anything, but it did not yield any results. In fact, Professor Allender and I decided that the reason we thought this problem was solvable via our approach might not be valid. So we decided to put this problem on pause and try working on something else. The new topic is the relationship between MKTP and MCSP. We are trying to find relationships between what classes the two problems are hard for. For the latter half of the week, I studied this topic with readings provided by Professor Allender.
- Week 4:
- After completing the readings from the previous week, Professor Allender and I started working on our new problem. We wanted to modify a theorem from a paper written by Allender and Hirahara so that it required fewer assumptions. There were two ways to do this. First, we tried to remove the logspace-uniformity of the reductions involved. We thought this would work because, given there exists such a non-uniform reduction, the oracle circuits that perform the reduction should be computable in exponential time (thus making it exponential time-uniform by default). I defined a machine that would do this to prove it would work, but then we realized it wouldn't lead to any interesting new conclusions, so we dropped that approach. Then, we focused on trying to get rid of the natural requirement for the theorem. This made us deviate from the proof in the paper because we could no longer cite a certain claim that required a natural reduction. We tried using properties of the oracle circuit and a random restriction to get rid of low threshold oracles, which would then allow us to make a claim similar to that made in the paper. I began reading papers that extended the isomorphism conjecture because the proof methods here were similar to what we wanted to do with our random restriction.
- Week 5:
- At the beginning of the week, Professor Allender realized that successfully proving our conjecture would have certain implications about the problem that were unlikely (or at least very hard to show). We decided that this was enough evidence to suggest working through this problem would not be worth it. So we began looking for a new problem to work on. At the same time, the Czech students had been working on two new models for SC2, what we called the "strong" and "weak" models, in order to supplement their exploration of the group isomorphism problem. These models used multiple existential and universal tapes which the machines could read in one direction once. These models theoretically should create their own SC2 hierarchies, and we wanted to find a way to classify these (What problems are hard for different levels of the hierarchies? Do either of the hierarchies collapse? Is there a relationship between the hierarchies or between one of the hierarchies and the polynomial hierarchy?). The Czech students found and proved a hard problem for one level in the strong hierarchy, and Professor Allender deemed the weak hierarchy unworthy of exploration due to its similarity to alternating Turing Machines. I then began looking into finding complete problems for other levels in the hierarchy with the preexisting complete problem as a basis.
- Week 6:
- Over the weekend, we began to worry that the strong hierarchy was pretty much the polynomial hierarchy but with some slight differences, but this wasn't resolved immediately. On Monday, we came up with a way to show that the strong hierarchy closely followed the polynomial hierarchy by looking at the containment of subsequent levels of one heirarchy in the next level of the other. At the same time, the Czechs decided that it was time to write up results to some of the other problems they worked on. Professor Allender gave Vasek and I a somewhat related problem: proving that ∃∀ 2SAT (as a DNF) is NP-complete, or, equivalently, that ∀∃ 2SAT (as a CNF) is coNP-complete. We know that the first is NP-hard, and the second is in coNP. So we either needed to prove containment for the first or hardness for the second. We chose the former. We tried to find a reduction from 3SAT to the 2SAT problem. The biggest roadblock we ran into was trying to create variables for the 2SAT instance that were universal (because, in this case, our 3SAT instance contains only existential variables, but our 2SAT instance contains both existential and universal variables). We were unable to solve the problem by the end of the week. Over the weekend, Professor Allender presented a proof that did not involve finding an explicit reduction.
- Week 7:
- During this week, I spent most of my time figuring out which problem I wanted to present on and preparing the presentation. I prepared a presentation both for the second problem I addressed (trying to better classify DSPACE by using PARITY reductions with MCSP and MKTP oracles). However, because this problem was likely a dead end, Professor Allender and I decided I should present on the new hierarchy findings that were made with the Czech students. I prepared and gave my presentation. After that, I spent the rest of the week looking into natural complete problems for our hierarchy. As a warmup, I was able to show that Vertex Cover, Graph Coloring, and Independent set had a natural logarithmic pathwidth reduction that made them complete for the first level of our hierarchy. I then began looking at higher levels of the hierarchy, as it would be more enlightening to find natural complete problems for those classes.
- Week 8:
- On Monday of this week, we traveled to Prague to begin the pre-conference lectures. Overall, the lectures were very good. I found the first lecture on graph homomorphisms the most intriguing. We also had a lecture on probabilistic graph theory on Thursday. During these days, we spent some time walking around the city and seeing places like the Prague Castle and the National Gallery. On Friday, we went to Ĉeský Krumlov, where we had the chance to explore another castle, go river rafting, and have our third lecture on partially ordered sets. This week I also began working on the final report.