Problems we assume are hard. Are they? ALSO- revised version of Demaine-Gasarch-Hajiaghayi is posted!

 (The latest version of 

Computational Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi is posted here. Its new and improved: (1) we have made all or most of the corrections send to us by proofreaders,  (2) there is a chapter on quantum computing, (3) there is an index.  Feel free to read it and send us corrections! 

This post is related to it in that most of the problems-assumed-hard mentioned in this post were the basis for chapters of the book.)

We think SAT is hard because (1) its NPC, and (2) many years of effort have failed to get it into P. 

Imagine a world where we didn't have the Cook-Levin Theorem. We may still think SAT is hard. We may even take it as a hardness assumption to prove other things hard by showing SAT \le A. We may also be curious if they are equivalent and have lots of reductions A \le SAT. The reductions might be Karp or Cook. 

You do not have to imagine this world! We already have it- in different contexts. In other areas of complexity theory there are problems that are assumed hard, but for which there is no analog of Cook-Levin. Are they hard? They seem to be- but the evidence is empirical. Not that there's anything wrong with that. 

I will list out problems that 

a) we assume are hard, for some definition of  we and hard.

b) we have NO proof of that and NO completeness or hardness result.  ADDED LATER- a commenter wanted me to clarify this.

 For SAT there is a well defined set of problems, NP, defined independent of any particular problem (that is, NP was NOT defined as all sets Karp-Red to TSP or anything of the sort) and by Cook-Levin we have 

if SAT is in P then NP is contained in P.

For FPT (the class the commenter was interested in) there IS the result

if weighed k-SAT is in FPT then W[1] is contained in FPT.

but W[1] is DEFINED as the set of problems FPT reducible to Weft-1 circuits (some books use a different basic problems) which IN MY OPINION is not a natural class. One may disagree with this of course. 

COUNTERAUGMENT: but W[1] Was defined as all problems FPT-reducible to Weft-1 circuits. And this is not the same 

(I do not include hardness assumptions for crypto because that's not quite the same thing. Also there are just so many of them!) 

I am sure I missed some- which is where YOU come in! Please leave comments with additional problems that I forgot (or perhaps did not know) to include. 

1) 1vs2 cycle: Given a graph that you are guaranteed is 1 cycle or the union of 2 cycles, determine which is the case. This is assumed to be hard to parallelize (we omit details of defining that formally).  This has been used for lower bounds in parallelism. See here.

2) 3SUM: Given x1,..,xn an array of integers, are there 3 that add to 0? There is an O(n^2) algorithm. The hardness assumption is that, for all epsilon, there is no O(n^{2-\epsilon}) algorithm. This assumption has been used to get lower bounds in comp. geom. See the Wikipedia entry here or the introduction of this paper here. (ADDED LATER, a 2-pager on some algorithms for 3SUM including some randomized ones: here. A commenter asked about randomized algorithms. Perhaps the conjecture should be that no randomized algorithm is sub quadratic.) 

4) APSP (All Pairs Shortest Path) Given a graph G, find for each pair of vertices  the length of the shortest path. There is an O(n^3) algorithm. The hardness assumption is that, for all epsilon, there is no O(n^{3-epsilon}) algorithm. This assumption has been used to get lower bounds on graph problems. For more details see the introduction of this paper: here

5)  Weighted-SAT-k: Given a Boolean formula (it can be taken to be in 2CNF form) is there a satisfying assignment that has exactly k of the variables set to TRUE. This is assumed to not be fixed parameter tractable (that is no function f such that this problem is in  O(f(k)n^{O(1)}) time). Problems that are FPT-equiv to it are called W[1]-complete and are all thought to not be in FPT. W[2], W[t] are also defined but we omit this. W[1]-complete has also been defined in other ways, but I can't seem to find a Cook-Levin type theorem for them. 

6) Graph Isom.  One of he few problems that are in NP but thought to not be NP-complete and, at least for now, is not in P. Babai has shown its in quasi-poly time (n^{(log n)^{O(1)}). There is a notion of GI-hard: problems that, if they are in P then GI is in P. See he Wikipedia entry here. Most of the GI-hard problems are variants of GI, e.g., graph isom. for directed graphs. GI could be in P without unbelievable consequences for complexity and without terrifying consequences for cryptography. 

7) Unique Games Conj: I won't define it formally here, see the Wikipedia entry here. From UGC you get several approximation results are optimal. Does that argue for UGC being true-- having consequences we believe? I would say YES since in some cases the algorithm that gives a good approx has an alpha-approx for some weird number alpha, and assuming UGC you get the SAME alpha as a lower bound. 

8) Existential  Theory of the Reals. Easier for you to read the Wikipedia entry here. It is used for problems that are inbetween NP and PSPACE. (ADDED LATER: One of the commenters says that Blum-Shub-Smale showed ETR is complete for the real version of  NP, so this item should not be on my list.) 

9) Orthogonal vector conjecture. See this paper: here. This is used to show problems are not in subquadratic time. 

Possible research directions and thoughts

a) Try to prove a Cook-Levin type theorem for one of these problems.

b) Build classes analogous to the poly-hiearchy on one of these problems.

c) Ask bounded-query questions. For example: Are k queries to 3SUM more powerful than k-1 (This is a VERY Gasarchian question.) 

d) Try to prove that one of these problems is actually hard. That seems hard. Perhaps on a weaker model (thats prob already been done for at least one of them.)