# Questions tagged [p-vs-np]

The tag has no usage guidance.

207 questions
Filter by
Sorted by
Tagged with
52 views

### Understanding P vs NP

I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
27 views

### How can I prove the following problem is NP?

Because of the covid-19 pandemic, our firm works semi-remote working. We want to that: Every day 2/5 of staff should be in the office. Everyone should go to the office 2 times a week. Teams want to ...
28 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 ...
76 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 ...
36 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 ...
112 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 ...
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$ ...
49 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). ...
97 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 ...
30 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 ...
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 ...
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 ...
122 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 ...
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 ...
484 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 ...
187 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 ...
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. ...
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 ...
83 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 ...
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 ...
58 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 ...
39 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?
77 views

### If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]

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?
57 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
48 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 ...
215 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 ...
51 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 (...
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, ...
50 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 ...
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 ...
29 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 ...
515 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 ...
132 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.
217 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-...
887 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 ...
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  that the problem to decide whether a given k-...
102 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 ...
115 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, ...
126 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 ...
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,...
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.
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 ? }$
73 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 ...
92 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. ...
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-...
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 ...
478 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 ...
129 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 ...
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 ...
### 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 ...