Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
157 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 ...
4
votes
3answers
125 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$ ...
1
vote
2answers
52 views

“Polynomial Counter” Turing Machine

I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
1
vote
2answers
75 views

P = NP ==> there exists no OWF: proof using NTM and binary tree

I read a proof in my script: If $P = NP\implies $ there exists no OWF $f$. A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$ Their proof was a bit messy so I want to ask if ...
0
votes
1answer
68 views

Assume P != NP, are these assertions valid?

Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$. Are the following assertions valid? $A \le_{P} B$ $B \le_{P} A$ My approach: $B \le_{P} A$ isn't valid, ...
3
votes
3answers
340 views

How are boolean circuits used for solving P vs NP?

In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to ...
1
vote
1answer
64 views

Proof plan for P ≠ NP

Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths. For each natural number $k$, we will have a formula $\phi$ of ...
0
votes
1answer
948 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
46 views

The subset sum problem is not in P because the question is about lossy compressed data? Why not?

Where is there a gap or error in my reasoning? The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1). The compression ...
4
votes
4answers
3k views

Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
1
vote
1answer
76 views

There is an $n^k$ prover if and only if $P = NP$

I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some ...
7
votes
0answers
40 views

P=NP turns 50. 1971 STOC conference

Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case ...
4
votes
1answer
69 views

How to prove that existence of one-way functions implies P≠NP?

Wikipedia: The existence of such one-way functions... would prove that the complexity classes P and NP are not equal. How is this proved?
1
vote
1answer
33 views

Is reduction symmetric?

I was watch this lecture https://youtu.be/moPtwq_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a ...
1
vote
0answers
25 views

Show that if vertex cover is reducible to a mod-inverse than P=NP

Let MOD-INVERSE consist of all pairs $\langle N,c \rangle$ such that $c$ has an inverse modulo $N$. Let VERTEX-COVER consist of all pairs $\langle G,k \rangle$ such that $G$ is an undirected graph ...
1
vote
1answer
57 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 ...
1
vote
1answer
101 views

$P = NP$, what am I missing?

First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
0
votes
1answer
54 views

If P = NP, do these NP-complete problems reduce to these specific easier versions?

I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al. Chapter 8 has the table below and I am wondering: if $P = NP$ does each of the problems on the left reduce ...
296
votes
7answers
140k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
-2
votes
2answers
109 views

Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ...
1
vote
2answers
100 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?
1
vote
1answer
32 views

Must an optimization problem with a greedy algorithm belong to P?

If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
-2
votes
1answer
133 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?
-2
votes
1answer
235 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.
1
vote
1answer
68 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 ...
4
votes
4answers
2k views

What is the evidence that P could equal NP?

What is the evidence that P could equal NP? I guess this is the same as asking: If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could ...
0
votes
0answers
34 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 ...
33
votes
3answers
3k views

Why is Relativization a barrier?

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to ...
2
votes
2answers
79 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
100 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 ...
0
votes
1answer
70 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
108 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
92 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
28 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
301 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
55 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 ...
-4
votes
1answer
221 views

Are all the NP-complete problems have strong reductions?

Are all the NP-complete problems have strong reductions? If I find a polynomial solution to one NP-complete problem, can I state that P = NP?
3
votes
1answer
527 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
249 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 ...
20
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. ...
9
votes
2answers
365 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 ...
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 ...
4
votes
2answers
266 views

Is it necessary for NP problems to be decision problems?

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems ...
0
votes
2answers
131 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
2answers
59 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
0
votes
0answers
27 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 ...
1
vote
1answer
55 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
219 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
58 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
2 3 4 5