Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
283
questions
-1
votes
2
answers
127
views
Will this proof method work for p vs np
Given, that NP is the class of all problems that a non-deterministic Turing machine can solve in polynomial time, and proving P = NP will prove that there is no difference between a non-deterministic ...
0
votes
1
answer
44
views
Can we use XOR's forced branching to show that NP!=P
Backstory: As happens, every now and then, one encounters an idea, prompting the question: Could I use this to prove that NP==P, or vice versa NP!=P
So then, today I got to trying to show that NP!=P ...
- 15
1
vote
1
answer
35
views
Prove that if P=NP then every two non trivial languages $A,B\in coNP$ holds $A \equiv_{P} B$
I need to prove that if $P=NP$ then every two non trivial languages (meaning not $\Sigma^*$ or $\varnothing$) $A,B\in coNP$ holds $A \equiv_{P} B$
(this means that $A \leq_{P} B$ and also $B \leq_{P} ...
- 117
-3
votes
1
answer
91
views
What is the P=NP? building?
I remember that I read somewhere some years ago that they've built a computing building with the 'P=NP?' question built in it from bricks so that they later have the option to rearrange these bricks ...
- 259
0
votes
1
answer
50
views
NP-Hard version of TSP if P=NP
If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only ...
- 3
0
votes
0
answers
56
views
Why can't we say that P=NP if we have an infinite text file with solution for every possible SAT combination?
I believe that I have a misunderstanding in the P=NP problem while I was thinking of how can it be proved in a non-constructive manner.
We know that we can build an infinitely large text file with ...
- 1
-2
votes
2
answers
106
views
Quasi polynomial algorithm for np complete problem
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
- 11
10
votes
4
answers
3k
views
Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?
Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP?
Thanks
- 349
0
votes
2
answers
37
views
how to polynomially check if a given boolean formula is unsatisfiable
Since SAT is np-complete, there is a polynomial algorithm to check if a given solution for any particular formula is correct. Just substitute the values and solve. But what if one claims that the ...
0
votes
0
answers
39
views
Proof Closer String/Consensus String/Center String is NP-hard
Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
- 23
2
votes
0
answers
33
views
How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it.
Fur-
thermore, if a polynomial worst-case time ...
- 203
-1
votes
1
answer
46
views
Natural combinatorial property in Natural Proofs
From Natual Proofs
Specifically, natural proofs prove lower bounds on the circuit complexity of boolean functions. A natural proof shows, either directly or indirectly, that a boolean function has a ...
- 11
1
vote
1
answer
79
views
Does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?
The class $\mathsf{NPO}$ is defined as optimization problems such that the corresponding decision problems defined with a threshold are in $\mathsf{NP}$.
Let $A$ be an optimization problem and $B$ a ...
- 16k
0
votes
1
answer
84
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
- 1
0
votes
1
answer
30
views
Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?
$f$ and $g$ being known functions.
We suppose that the problem is solvable.
To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
- 11
1
vote
1
answer
112
views
If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?
First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
- 11
0
votes
2
answers
190
views
( Soft question ) P vs NP - is such a situation possible?
Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
0
votes
1
answer
174
views
3sat to clique reduction program
I am searching for a program to convert 3sat to clique problem.
I tried following links
https://www.geeksforgeeks.org/maximal-clique-problem-recursive-solution/
https://www.geeksforgeeks.org/find-all-...
- 1
0
votes
2
answers
83
views
Is there a challenge with which one could reasonably show to have found a feasible polynomial algorithm for an NP problem?
Say there is someone claiming to have solved P vs NP, by finding a (computationally feasible, i.e. no huge constants) polynomial solution to a problem in NP:
Apart from a formal proof, is there any ...
- 101
0
votes
0
answers
35
views
Does the following down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"?
Does the following highly down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"? If not, why not?
Marek, V. Wiktor. Introduction to Mathematics of
...
- 154
1
vote
0
answers
63
views
Is NP a subring of the 2-adic integers?
Let me take the set $A = \{1, 2\}$ as the alphabet. By the bijective binary numeral system, $A^*$ has one-to-one correspondence to the set of nonnegative integers $\mathbb{N}$. As such, each language $...
- 367
0
votes
1
answer
49
views
Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$?
Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ?
I found a proof with padding arguments (wikipedia), that
$$ P = NP \Rightarrow EXP = NEXP $$
If an oracle $A$ exists with $P=NP$ ...
1
vote
1
answer
177
views
What could $P = NP$ imply about arbitrary Turing machines?
My question:
What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
- 11
0
votes
1
answer
43
views
Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?
I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$.
What is known is that the ...
user154939
1
vote
0
answers
199
views
if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)
$L^\complement$ = the complement of L
is it true that if
$L\in NPComplete $
and
$L\leq_p L^\complement \rightarrow P=NP$
basically asking if the following statements are correct
$if (L\in NPComplete ) ...
- 53
2
votes
1
answer
337
views
if P = NP, does it mean that P = NP = NP-complete?
Lets assume P = NP, so all problems in NP are decidable in polynomial time,
Therefore I can solve all problems in NP in polynomial claiming P = NP = NPC.
But then, how come Σ* belongs to P = NPC ...
- 23
0
votes
3
answers
116
views
If X is poly-time reducible to Y and X is in P, then Y is in P
The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
1
vote
1
answer
55
views
Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?
The problem of Oracle-SAT is given below:
Given oracle query access to some machine, $U$ that has $2^N$ inputs, determine if there is an input such that the machine accepts.
This is very similar to ...
- 253
1
vote
0
answers
42
views
Is Quantum Search (SAT with only oracle access) NP-hard (and not NP-complete)?
Quantum search differs from the standard boolean SAT as it is restricted to only oracle calls to a circuit (or CNF formula). Where SAT gives us the structure of a formula (however loosely defined that ...
- 253
3
votes
3
answers
175
views
Are there problems in NP that would solve P vs NP, but are not NP complete
NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some ...
- 253
-1
votes
2
answers
70
views
Is One Way TSP NP-Complete?
I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a ...
- 103
0
votes
1
answer
265
views
If P=NP then all languages in P are NP-complete?
I know that if $P=NP$ then all of the languages in $NP$ are $NP-Complete$, but what about those in $P$?
I assume yes, because $P \subseteq NP$, but I just want to check.
Thanks!
- 47
0
votes
1
answer
96
views
Using undecidability to prove P != NP
Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability within an NP problem to ensure that we can ...
- 1
0
votes
2
answers
45
views
Are there any other language classes of time complexity between the P language class and the NP language class?
$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine.
$NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and ...
- 315
-1
votes
2
answers
61
views
Does superpolynomial lower bounds of a problem in $NP$ mean that $P \neq NP$?
If one proves that the lower bounds of an $NP$ problem, are not bounded by any polynomial, is this enough to prove that $P$ does not equal $NP$?
- 1
3
votes
1
answer
132
views
Why is this a flawed counterexample to P=NP?
I apologize in advance for asking this, since I'm sure this site is flooded by amateurs like me asking about P and NP. If there's a better platform to ask this on, please let me know, but this ...
- 150
3
votes
3
answers
238
views
Question about the Relativization barrier
Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem
with methods like ...
1
vote
3
answers
118
views
Problems Solvable in Poly time but not verifiable in Poly time
I was just wondering if there exists problems that are solvable in polynomial time (a correct solution can be found in polynomial time) but not verifiable in polynomial time. My professor says no, but ...
2
votes
2
answers
251
views
Why does showing that a NP problem is not NP-complete implies P$\neq$NP?
I found in this answer that if a problem is shown to be NP but not NP-complete then P$\neq$NP. What is the argument to prove this statement?
- 36
1
vote
1
answer
32
views
In NP-hardness, can any category reduce to itself? How can you intuitively explain which categories reduce to the others?
I'm trying to understand how problems in NP-hardness reduce to one another. As I understand it now, if X reduces to Y, Y is at least as hard as X.
What I think that means, and would like confirmed or ...
- 11
0
votes
1
answer
54
views
P = NP: Doesn't a search generate more information than a check?
I feel like I am understanding P ≠ NP fairly well, but there is one issue I feel like I am missing. It seems like a search for an answer generates information that a check does not.
Is this a correct ...
0
votes
1
answer
212
views
Why solving #2SAT in polynomial time implies P = NP?
The wikipedia article for #P states that if we have a polynomial-time algorithm for a #P-complete problem, P = NP is true.
As #2SAT is #P-complete, this would mean that providing a polynomial-time ...
- 195
0
votes
1
answer
65
views
Set of Turing machines that accepts at least one input in bounded time
What is known about the languages:
$$S_f = \{ [M] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|[M]|) \ \text{steps}, \\ \ |x| \leq f(|[M]|) \}$$
I used to think that in ...
- 177
0
votes
4
answers
240
views
Why do some "common sense" $P \ne NP$ arguments seem to disregard high-degree polynomials?
I've seen arguments for $P \ne NP$ that rely on certain intuitions about how the real world actually is, generally making the point that it "makes sense" that there exist problems which have ...
1
vote
1
answer
74
views
Is ANF-SAT P or NP?
Given a finite set of equations in ANF, for example:
$$
\begin{cases}
(x_1 \land x_2) \oplus (x_1 \land x_3 \land x_4) \oplus 1 = 0 \\
x_3 \oplus (x_2 \land x_3 \land x_4) = 0 \\
(x_1 \land x_4) \...
- 13
4
votes
1
answer
76
views
Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?
One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many ...
0
votes
1
answer
53
views
P vs. NP problem and understanding "worst case complexity"
Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
- 291
1
vote
1
answer
137
views
Unpacking the notion of "hardest instances" for NP-complete problems
Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...
- 291
0
votes
0
answers
54
views
Could we know what's the total number of unsatisfiable 3SAT formulas for a given n variables?
given some $n$ variables I would be interested to know what is the count of all 3SAT formulas under $n$ that are unsatisfiable.
An example of all 3SAT forumlas under $n=3$ is the following:
$$
( x \...
0
votes
2
answers
67
views
How could NP-complete problems be in P?
I've learned some basics about P and NP. Please excuse if the following is not very precise.
I've read that NP-complete problems are the hardest problems in NP. (Is that correct?)
But now I'm ...
- 170