Questions tagged [p-vs-np]
The p-vs-np tag has no summary.
297 questions
-3
votes
1
answer
163
views
Is P vs. NP solved?
I read the paper Xe, Zhou:SAT requires exhaustive search. Does this paper solve the P vs. NP problem?
0
votes
1
answer
81
views
3-CNF to 2-CNF reduction
I want to start by saying that I've struggled to find any satisfying answer to this question of mine. I did read this question, but it's slightly different.
My idea is simply that every 3-cnf formula ...
- 101
0
votes
2
answers
109
views
Transform NAND gate to xorsat
Is it possibile to construct an xorsat problem with n variables that has as solutions only (0,1,...),(1,0,...),(0,0,...)? By dots, I meam the values of auxiliary variables, and these 3 vectors are the ...
2
votes
1
answer
103
views
NP-Completeness of the Rectangle Packing Puzzles
I'm reading the proof of the (strongly) NP-completeness of the Rectangle Packing Puzzles by Erik D. Demaine, Martin L. Demaine (source: https://erikdemaine.org/papers/Jigsaw_GC/paper.pdf).
...
0
votes
2
answers
72
views
The Delemma of non-determinsitc Machines
I saw a YouTube video about non-deterministic random access machines (NRAM).
An NRAM works like a deterministic RAM with an additional command called 'if_better'.
https://www.youtube.com/watch?v=...
4
votes
2
answers
2k
views
Are all problems in P reducible to each other and equally difficult?
Can every problem $ A \in P $ be reduced to any other problem $ B \in P $? If so, does that mean all problems in $ P $ have the same level of difficulty? Does this also hold for other complexity ...
- 55
1
vote
1
answer
190
views
Why is P = PSPACE, if P = NP?
I understand that we have the inclusions $P \subseteq NP \subseteq PSPACE$ . If we assume $ P = NP$ , this means that every problem in NP can be solved in polynomial time by a deterministic Turing ...
- 55
0
votes
1
answer
119
views
Why we need the assumption P=NP for this problem?
There is a famous problem that we can prove that if $P=NP$, then any non-trivial language $A \in P$ is NP- complete.
The proof idea was to use non- triviality of $A$. So we say that as $A$ is non-...
- 39
1
vote
1
answer
80
views
What is the point of proof of correctness of NP-completeness?
In most the problems I am tasked to prove that a problem A is NP-complete. I show that B is in NP, then I reduce NP-hard problem A to B. Then I am required to prove that a yes instance in B is a yes ...
- 31
0
votes
1
answer
92
views
how to show that if $L'\in \text{P}\iff \text{P}=\text{NP}?$
I have one small question.
If $L'\in \text{NP}$ and for all $L\in \text{NP}$ such that $L\leq_p L'.$
My question is, how to show that if $L'\in \text{P}\iff \text{P}=\text{NP}?$
It's obvious by ...
- 27
-1
votes
1
answer
50
views
Complexity Class of Language L: Formula in CNF and DTM Consistency with Variable Assignments
L = {⟨F, M⟩: F is a formula in CNF, M is a DTM,
and for every assignment A to the variables of F, M(A) = F[A]}.
is it in
P, NP ∩ co-NP, NP, co-NP, R, RE, co-RE, RE ∪ co-RE Complement
thanks
0
votes
2
answers
100
views
Why is it inconceivable that a problem is in P but not in NP?
It is my understanding that if a problem has several solutions, then
the problem is in P if at least one of the solutions can be found in polynomial time,
the problem is in NP if each of the ...
- 103
0
votes
0
answers
47
views
if P≠NP then does P ≠ coNP?
If P ≠ NP then does P ≠ coNP?
If so please explain why?
I have tried thinking about subsets between langauges, but not sure where to start.
1
vote
1
answer
130
views
$f$ is Reduction from $\texttt{INDSET}$ to itself
My teacher said in his lecture( followed by the book Barak and Arora) the following:
We will imagine that a shocking discovery reveals that there exists a function $f$, thinking in linear time, so ...
user150715
0
votes
0
answers
103
views
Using interdependent 2 sat to find if a possible number is valid in sudoku
Has there been any papers or books covering using 2sat in an interdependent way to find if a possible number in a sudoku cell is valid.
What I have so far is this off the ai I wanted to read more on ...
