Questions tagged [p-vs-np]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
275 views

P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: P=NP \implies \forall k\ \exists j.\ \...
203 views

Are there consequences for P ≠ NP that are unintuitive?

It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
54 views

Is anything known about the structure of sets of valuations representable by 3CNF formulas?

Let's suppose we have propositional variables $x_1 ... x_n$. A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$. So, there are $2^n$ possible ...
147 views

P vs. NP and Godel's Theorems

This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct. Basically, I'm wondering if it is plausible for there to be a formal proof ...
73 views

What can be a Zero Knowledge Proof of a working SAT Algorithm?

Me and my colleague are exploring new ideas to solve SAT efficiently (i.e. in polynomial time) and it's the case that there is a candidate algorithm. Unfortunately, neither of us can write scripts ...
157 views

Is valid the notion of infinity for the NP-complete problems?

We have defined two complexity classes which have a close relation with the notion of infinity. The first one is: We say that a language $L$ belongs to $UP_{\infty}$ if there exist an infinite ...
397 views

Show that P is a subset of NP

Okay, before I start with the question I would like to point out that I am aware that there are many proofs of this question online. However, I am interested in showing this with the definitions of my ...
94 views

Consequences from a lower bound of SAT problem

I'm not sure how lower bounds affect the question to the P=NP problem. I.e. : Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3. If you find a ...