1
$\begingroup$

Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. 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?

$\endgroup$
  • 2
    $\begingroup$ what's the question ? the article has a long list anyway. Provide a link for the column, please. $\endgroup$ – Suresh Venkat Aug 26 '10 at 19:30
  • 1
    $\begingroup$ And at the very least, this should be "community wiki". $\endgroup$ – Jukka Suomela Aug 26 '10 at 20:47
  • 1
    $\begingroup$ The term "complexity lower bounds" means in many (or most?) occasions unconditional lower bounds (like circuit size lower bounds). So the question is unclear. $\endgroup$ – Iddo Tzameret Aug 26 '10 at 23:45
  • $\begingroup$ Please make it CW if required. $\endgroup$ – Mohammad Al-Turkistany Feb 10 '11 at 17:13
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 10 '11 at 17:24
5
$\begingroup$

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 for a list of consequences.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 10 '11 at 17:19
3
$\begingroup$

This isn't mentioned in the article, but the exponential time hypothesis is very useful for proving exponential lower bounds on the running time of hard problems.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.