Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
205
questions
1
vote
1answer
23 views
3Col reduction Variation, Special edges
I have a question concerning NP reduction.
My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
2
votes
2answers
64 views
proving that a problem is in P
I read online that this problem is in P:
Problem = {a^n, where n is a primary number}
I can't find any algorithm that decides if a word w in ...
0
votes
0answers
20 views
Why does converting a NDTM to a a DTM result in a higher time complexity?
I feel like I am really close to understanding the difference between P vs NP, and I think it comes down to this. The confusion stems from the fact that both P and NP problems are done in polynomial ...
1
vote
1answer
110 views
Is there a TM that halts iff P = NP?
Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is ...
2
votes
2answers
77 views
Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)
In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are
Constant time $\mathcal{O}(1)$: Ex sum of first $n$ ...
0
votes
1answer
41 views
Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard
The algorithm needs to generate all possible combinations from a given list (empty set excluded).
...
0
votes
2answers
95 views
How would it be possible that primality testing is in P, but not factorization?
Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of ...
-1
votes
1answer
27 views
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
0
votes
1answer
26 views
P vs NP characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could ...
0
votes
0answers
26 views
Are inputs of NP problems too implicit?
I'm reading on wikipedia about P vs NP and I have a question.
Consider the zero sum problem: given a set of integer A, determine if there is a non empty subset such that the sum of all its elements is ...
2
votes
1answer
114 views
If P=NP, does this imply that all problems are NP-hard?
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible ...
1
vote
1answer
53 views
While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?
While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
2
votes
1answer
480 views
Does P = NP in Cellular Automata of Hyperbolic Spaces?
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP ...
-1
votes
3answers
171 views
Why don't passwords prove P != NP?
Pardon my ignorance on the matter but,
Verifying passwords = Polynomial (linear)
Guessing passwords = Exponential
Since each guess has nothing to do with one another, exponential time is best possible ...
19
votes
4answers
3k views
How hard would it be to state P vs. NP in a proof assistant?
GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed Pā NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. ...
0
votes
0answers
47 views
Is a or free SAT formula NP complete?
Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $.
Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
0
votes
2answers
77 views
If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
If problem B is in P and A reduces to B, then problem A is in P.
Problem B is NP-complete ...
0
votes
0answers
26 views
$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there ...
0
votes
1answer
43 views
If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we ...
-1
votes
1answer
35 views
If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?
If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
-3
votes
1answer
41 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
Is this true, false or "we don't know"? Why?
-1
votes
2answers
53 views
How to prove P = NP if problem Ī Ļµ NP-complete and Problem complement Ī c Ļµ NP?
How to prove if P = NP if problem Ī Ļµ NP-complete and Problem complement Ī c Ļµ NP?
OR
P = NP if NPC intersects with Co-NPC
1
vote
1answer
47 views
What is and amplification factor in pseudo-random generators?
I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this ...
-1
votes
2answers
212 views
Review my proof that Co-NP != P
This is hobby level work, not my job. I wrote this excerpt to share some ideas about Co-NP.
The idea is to pick a problem category in Co-NP, where the correct answer is hard to verify because of ...
0
votes
3answers
50 views
Is it possible that Co-NP = P but NP != P
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
1
vote
1answer
61 views
P=NP when number of inputs that give 1 is bounded by polynomial
Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
1
vote
1answer
44 views
Can you apply neural networks to design algorithms?
Iām kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math ...
2
votes
2answers
353 views
P vs NP and Angle Trisection (serious question)
I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.
My understanding from many popular-level sources (like Scott ...
0
votes
0answers
27 views
How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?
The exponential-time hypothesis posits that if $\mathsf{3SAT}$ has NO subexponential time algorithm (i.e. one in $\mathcal O(2^{o(n)})$), then $\mathsf{P}\neq \mathsf{NP}$.
However, I am interested ...
0
votes
1answer
419 views
Prove or disprove, If A ā¤p B and B is NP-hard, then A is in NP-hard
Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.
How do I formally disprove ...
0
votes
1answer
100 views
Prove or Disprove, 3SAT ā¤p 2SAT, then P = NP
I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
2
votes
1answer
212 views
Would a sparse NP-Complete language imply L = NP?
Would a sparse NP-Complete language imply L = NP?
Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-...
7
votes
1answer
878 views
Algorithms that run in polynomial time if P=NP
On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
0
votes
1answer
29 views
If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?
Deciding bipartite hypergraph coloring is NP-hard:
While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
1
vote
1answer
86 views
Time complexities of state-of-the-art SAT solvers with respect to length of the formula
I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.
If I am not mistaken, one of the reasons why most believe P does not ...
1
vote
3answers
82 views
NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution
The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.
My question is, ...
-1
votes
1answer
123 views
Showing on-line P = NP
I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations.
Following that, I ...
24
votes
5answers
8k views
P = NP clarification
Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example.
My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
1
vote
1answer
2k views
A problem in NP but not NP-complete?
Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
0
votes
1answer
55 views
how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$
how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then
${NP = P ? }$
2
votes
1answer
70 views
How to know if a problem belongs to NP Class?
What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
0
votes
1answer
89 views
P Vs NP can never be proven one way or the other!
Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.
And since if we prove that any problem in NP is a P that would mean that we have NP=P.
...
0
votes
1answer
48 views
Does computational complexity theory take into account problems with subjectivity in the verification of a solution?
When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time).
But in both cases these are black-and-...
5
votes
3answers
3k views
If a problem is in P solved via dynamic programming, is it also in NP?
So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.
My answer is, "Since it is also polynomial ...
0
votes
1answer
423 views
How to prove Exact cover problem is NP Complete using Vertex Cover problem?
Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
0
votes
1answer
128 views
Is this statement of P = NP in Agda correct?
Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below).
The statement here does seem to express the ...
1
vote
0answers
36 views
Weaker conjectures to prove in order to arrive at P =/= NP
We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the ...
2
votes
1answer
71 views
How is $\text{PCP}[O(\log n),O(1)]$ NOT P?
As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.
For $\text{PCP}[O(\log n),O(1)]$, won't there just be ...
0
votes
0answers
43 views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
0
votes
1answer
197 views
Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B
I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].
Why Isn't this ...
