Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

10
  • 1
    $\begingroup$ cstheory.stackexchange.com/q/27215/5038, cstheory.stackexchange.com/q/11422/5038, cstheory.stackexchange.com/q/2271/5038 $\endgroup$ Commented Sep 22, 2016 at 19:11
  • 1
    $\begingroup$ To clarify, it seems like the question is more about parameters of multi-parameter problems than it is about witnesses? For example, SAT can be considered parameterized by how many literals and what the formula is itself, so you're asking if there's a relationship between these two parameters that is required for the "hardness" of the problem. So for example, one potential answer (that i just made up and is not correct) might be that SAT is only hard if there's atleast twice as many clauses as there are literals, but less than 4 times as many. Is this the right idea? $\endgroup$ Commented Sep 22, 2016 at 19:21
  • $\begingroup$ Yes this sounds like what I'm interested in. In some sense this is a relation between the formula and the witness size, since the witness size equals the number of literals, no? $\endgroup$ Commented Sep 22, 2016 at 19:23
  • $\begingroup$ What you should really be asking is how long the witness has to be for the problem to become easy (there is a polytime algorithm for verifying the witness, and there always exists a witness of size at most $f(n)$). $\endgroup$ Commented Sep 22, 2016 at 19:30
  • 1
    $\begingroup$ You're assuming that the witness has to be a satisfying assignment (for SAT), a clique (for clique), and so on. But we don't know that. It seems like you're interested in the complexity given some parameter. $\endgroup$ Commented Sep 22, 2016 at 20:43