2022 Developer Survey is open! Take survey.

Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 views

Are there computational complexity results for generative adversarial networks?

First time posting on here; if this question is too rough I would appreciate if you could point me to a stackexchange forum where this question may be a better fit. Generative adversarial networks (...
user avatar
1 vote
1 answer
27 views

Proving 2SAT is in P vs algorithm for finding a satisfying assignment

I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
user avatar
  • 113
2 votes
0 answers
14 views

Understanding a black-box vs white-box simulation and relativization

I am trying to understand the relativization barrier from Baker Gill Solovay (BGS). About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
user avatar
0 votes
0 answers
35 views

If P = NP then EXP^P = NEXP^NP?

I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
user avatar
2 votes
2 answers
99 views

What if solving P vs NP revealed a contradiction?

Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was ...
user avatar
2 votes
1 answer
34 views

What is the exclusion-inclusion algorithm for TSP?

I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$. Specifically: "This bound has ...
user avatar
0 votes
2 answers
87 views

Can we DISPROVE that a problem is NP-complete

So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
user avatar
  • 1
1 vote
1 answer
48 views

Is proving NP-(in)completeness generally NP-complete?

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
user avatar
  • 161
-2 votes
2 answers
143 views

If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?

The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
user avatar
0 votes
1 answer
21 views

Understanding P, NP with an example decision problem

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
user avatar
  • 3
0 votes
1 answer
41 views

Reduction of np to npc

Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not? My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
user avatar
  • 1
1 vote
1 answer
42 views

In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?

This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
user avatar
1 vote
1 answer
92 views

Is $P=NP$ even if we need infinitely many algorithms?

If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$? More specifically, what if there were infinitely many ...
user avatar
1 vote
2 answers
45 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
user avatar
-5 votes
1 answer
71 views

Really confused

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this? P = NP P ⊊ NP P ≠ NP NP ⊆ P
user avatar
-4 votes
3 answers
96 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
user avatar
1 vote
2 answers
92 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 ...
user avatar
  • 25
1 vote
2 answers
101 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$ ...
user avatar
  • 13
0 votes
1 answer
73 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, ...
user avatar
1 vote
1 answer
72 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 ...
user avatar
  • 169
0 votes
1 answer
58 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 ...
user avatar
  • 33
4 votes
4 answers
4k 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=...
user avatar
1 vote
1 answer
88 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 ...
user avatar
7 votes
0 answers
52 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 ...
user avatar
4 votes
1 answer
105 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?
user avatar
  • 413
2 votes
1 answer
107 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 ...
user avatar
  • 219
1 vote
0 answers
34 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 ...
user avatar
  • 31
1 vote
1 answer
116 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 ...
user avatar
  • 13
0 votes
1 answer
183 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 ...
user avatar
-2 votes
2 answers
174 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 ...
user avatar
  • 11
1 vote
1 answer
65 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 ...
user avatar
1 vote
1 answer
114 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 ...
user avatar
  • 65
0 votes
0 answers
36 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 ...
user avatar
1 vote
1 answer
133 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 ...
user avatar
  • 11
2 votes
2 answers
87 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 ...
user avatar
2 votes
3 answers
227 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 ...
user avatar
4 votes
3 answers
140 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$ ...
user avatar
  • 519
0 votes
1 answer
134 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). ...
user avatar
  • 13
0 votes
2 answers
137 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 ...
user avatar
  • 683
-1 votes
1 answer
155 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 ...
user avatar
  • 168
0 votes
1 answer
36 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 ...
user avatar
  • 133
2 votes
1 answer
942 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 ...
user avatar
1 vote
1 answer
65 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 ...
user avatar
3 votes
1 answer
567 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 ...
user avatar
  • 1,873
-1 votes
3 answers
347 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 ...
user avatar
21 votes
4 answers
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. ...
user avatar
  • 325
0 votes
0 answers
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 ...
user avatar
  • 147
0 votes
2 answers
271 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 ...
user avatar
1 vote
2 answers
125 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?
user avatar
-2 votes
1 answer
241 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?
user avatar

1
2 3 4 5