Questions tagged [p-vs-np]

The tag has no usage guidance.

276 questions
Filter by
Sorted by
Tagged with
68 views

Is P=NP either false or independent of ZFC axioms of mathematics?

A discussion is given on the home page of professor S Gill Williamson UCSD CSE but not resolved there: search for "s gill williamson" seventh topic down.
15 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 ...
855 views

P vs NP problem (Student example)

Hello dear stackexchangers, I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-...
28 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 ...
75 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 ...
35 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 ...
1 vote
67 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 ...
49 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 ...
137 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 ...
343 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 ...
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 ...
1 vote
54 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 ...
104 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
77 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 ...
74 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-...
31 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 ...
1 vote
63 views

318 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 ...
20 views

reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
226 views

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
50 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 ...
35 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 ...
42 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 ...
60 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 ...
178 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!
220 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 ...
75 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 ...
88 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 ...
60 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$?
117 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 ...
1 vote
116 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 ...
200 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?
1 vote
30 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 ...
47 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 ...
156 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 ...
389 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.
64 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 ...
1 vote
59 views