<p>The unique games conjecture has recently been one of the most fruitful assumptions for proving good lower bounds, although it is more controversial than most assumptions about complexity class separation.  See <a href="http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf">On the Unique Games Conjecture</a> for a list of consequences.</p>

CC BY-SA 2.5
2011-02-10T17:19:04.633Z
UGC is very nice, but I am not sure if this answer fits the question.  I do not think that the term “complexity lower bound” usually includes hardness based on reducibility such as NP-hardness or UG-hardness.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-26T20:42:45.440Z
2010-08-26T20:42:45.440Z
Ian
<p>This isn't mentioned in the article, but the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow">exponential time hypothesis</a> is very useful for proving exponential lower bounds on the running time of hard problems. </p>

CC BY-SA 2.5
2010-08-27T02:36:46.627Z
2010-08-27T02:36:46.627Z
Robin Kothari
<p>The polynomial hierarchy is infinite. This implies other conjectures that are often used, like NP is not in coAM, NP is not equal to coNP, etc.</p>

CC BY-SA 2.5
2010-08-27T02:46:05.550Z
2010-08-27T02:46:05.550Z
Robin Kothari
<p>Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's <a href="http://www2.research.att.com/~dsj/columns/col25.pdf" rel="nofollow">NP-Completeness Column 25</a>. What are the other major conjectures not mentioned in the above article? Did we achieve some progress towards proving one of these conjectures? Which conjecture do you think would require completely different techniques from the currently known ones?</p>

CC BY-SA 2.5
2011-02-10T17:13:10.430Z
Please make it CW if required.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-10T17:24:17.013Z
The current question (revision 4) is much more interesting than the previous revisions, but it is broad.  I think that you are putting too many things in one question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-26T19:30:45.897Z
what's the question ? the article has a long list anyway. Provide a link for the column, please.
Suresh Venkat
CC BY-SA 2.5
2010-08-26T20:47:50.410Z
And at the very least, this should be "community wiki".
Jukka Suomela
CC BY-SA 2.5
2010-08-26T23:45:26.470Z
The term "complexity lower bounds" means in many (or most?) occasions unconditional lower bounds (like circuit size lower bounds). So the question is unclear.
Iddo Tzameret
<cc.complexity-theory><lower-bounds>
Major conjectures used to prove complexity lower bounds?
Mohammad Al-Turkistany
# Major conjectures used to prove complexity lower bounds?

(Asked by: username_0 on 2010-08-26)

Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's [NP-Completeness Column 25](http://www2.research.att.com/~dsj/columns/col25.pdf). What are the other major conjectures not mentioned in the above article? Did we achieve some progress towards proving one of these conjectures? Which conjecture do you think would require completely different techniques from the currently known ones?

**Tags:** cc.complexity-theory, lower-bounds
> **Comments:**
> **username_2**: what's the question ? the article has a long list anyway. Provide a link for the column, please.  
> **username_3**: And at the very least, this should be "community wiki".  
> **username_4**: The term "complexity lower bounds" means in many (or most?) occasions unconditional lower bounds (like circuit size lower bounds). So the question is unclear.  
> **username_0**: Please make it CW if required.  
> **username_1**: The current question (revision 4) is much more interesting than the previous revisions, but it is broad.  I think that you are putting too many things in one question.  

---

## 3 answers

### Answer by username_5 on 2010-08-26. Score: 5

The unique games conjecture has recently been one of the most fruitful assumptions for proving good lower bounds, although it is more controversial than most assumptions about complexity class separation. See [On the Unique Games Conjecture](http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf) for a list of consequences.

> **Comments:**
> **username_1**: UGC is very nice, but I am not sure if this answer fits the question.  I do not think that the term “complexity lower bound” usually includes hardness based on reducibility such as NP-hardness or UG-hardness.  

---

### Answer by username_6 on 2010-08-27. Score: 3

This isn't mentioned in the article, but the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) is very useful for proving exponential lower bounds on the running time of hard problems.


---

### Answer by username_6 on 2010-08-27. Score: 1

The polynomial hierarchy is infinite. This implies other conjectures that are often used, like NP is not in coAM, NP is not equal to coNP, etc.


---

