This new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a conjunction of boolean formulas. obviously this problem is not in NP, or it would be a P≠NP proof. But the paper does not give its known complexity class.

What time complexity class is this problem of finding solutions to conjunctions of boolean formulas in?

Also looking for any other context wrt known theory to place this paper result in, i.e. How does it mesh with other known results etc.

  • 3
    $\begingroup$ Why is the problem of deciding if there is a solution to a conjunction of boolean formulas not in NP? $\endgroup$ – Juho Jun 27 '14 at 5:25
  • $\begingroup$ ok J touché you got me that should read NP complete $\endgroup$ – vzn Jun 27 '14 at 14:52
  • 2
    $\begingroup$ Please specify the problem that you want to know the complexity of, in the question, explicitly. Right now the problem isn't clear to me. We shouldn't have to read the paper to work out problem you are referring to; the question needs to be self-contained. Also please define what you mean by "finding solutions to". $\endgroup$ – D.W. Jun 27 '14 at 16:48
  • 3
    $\begingroup$ vzn, please try to read my comment more carefully. I didn't say that questions cannot be inspired by or based upon CS papers. I said that questions need to be self-contained. Think about it this way: do you want people to answer your question, or not? If you want people to answer your question, why would you put extra unnecessary barriers in the way of understanding what you are even asking? Please spend more time figuring out how to frame your question precisely, then edit your question accordingly. $\endgroup$ – D.W. Jun 27 '14 at 16:57
  • 1
    $\begingroup$ @vzn, if my answer does not answer your question, please don't accept it. I'm not grubbing for points. I really don't care about rep. What I do care about is maintaining the quality of questions and answers on this site. Questions that are vague or unclear waste readers' time and do not contribute to our site's mission of building an archive of high-quality questions and answers that will be useful to others. Others have expressed similar sentiments to you before; allow me to add my voice as well. $\endgroup$ – D.W. Jun 27 '14 at 18:27

Assuming your boolean formulas have no quantifiers (just AND, OR, NOT, etc.), testing validity of a conjunction of boolean formulas is in NP. It is in fact NP-complete.

  • $\begingroup$ its apparently for formulas that dont share variables in each formula ie are independent. yes the standard/common version of the problem is as you state. $\endgroup$ – vzn Jun 27 '14 at 16:50
  • $\begingroup$ lol on stackexchange its always the questioners fault isnt it! $\endgroup$ – vzn Jun 27 '14 at 17:16
  • $\begingroup$ @vzn If omissions in the questioner's question are not the questioner's fault, whose fault are they? $\endgroup$ – David Richerby Jun 27 '14 at 21:20
  • $\begingroup$ @DavidRicherby any omissions are in the eye of the beholder. & anyway so maybe one should just eliminate the highly critical middlemen & answer ones own questions! $\endgroup$ – vzn Jun 27 '14 at 22:11

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