Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
29 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 ...
Sachin's user avatar
  • 1
0 votes
1 answer
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 ...
someone's user avatar
1 vote
1 answer
52 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 ...
someone's user avatar
0 votes
2 answers
96 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 ...
Aditya Mishra's user avatar
0 votes
1 answer
47 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-...
user's user avatar
  • 1
0 votes
1 answer
60 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 ...
tistorm's user avatar
  • 101
0 votes
0 answers
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 ...
Geremia's user avatar
  • 146
1 vote
0 answers
63 views

Is NP a subring of the 2-adic integers?

Let me take the set $A = \{1, 2\}$ as the alphabet. By the bijective binary numeral system, $A^*$ has one-to-one correspondence to the set of nonnegative integers $\mathbb{N}$. As such, each language $...
Dannyu NDos's user avatar
-1 votes
0 answers
23 views

Can irreversibility show that P ≠ NP?

Can the fact that there are irreversible operations show that P ≠ NP? It seems all algorithms in P are reversible, and all algorithms in NP are irreversible.
Geremia's user avatar
  • 146
0 votes
1 answer
29 views

Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$?

Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ? I found a proof with padding arguments (wikipedia), that $$ P = NP \Rightarrow EXP = NEXP $$ If an oracle $A$ exists with $P=NP$ ...
Reiner Czerwinski's user avatar
1 vote
1 answer
163 views

What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
Axid Ubish's user avatar
0 votes
1 answer
37 views

Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?

I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$. What is known is that the ...
user avatar
1 vote
0 answers
99 views

if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)

$L^\complement$ = the complement of L is it true that if $L\in NPComplete $ and $L\leq_p L^\complement \rightarrow P=NP$ basically asking if the following statements are correct $if (L\in NPComplete ) ...
Skynet's user avatar
  • 53
2 votes
1 answer
296 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 ...
Shy Cohen's user avatar
0 votes
0 answers
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-...
user's user avatar
  • 1
0 votes
3 answers
98 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 ...
Uzair Siddiqui's user avatar
1 vote
1 answer
49 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 ...
Loic Stoic's user avatar
0 votes
0 answers
31 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 ...
Loic Stoic's user avatar
1 vote
2 answers
73 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 ...
Loic Stoic's user avatar
-1 votes
2 answers
59 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 ...
Darcy Sutton's user avatar
0 votes
1 answer
138 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!
Geo's user avatar
  • 37
0 votes
0 answers
34 views

P versus NP relative to a P-complete set

If one can prove $P^A \not= NP^A$ for a P-complete oracle $A$, does this imply $P\not=NP$. I believe, that $P\not=NP$ relative to a P-complete oracle would mean $P^P \not= NP^P$. And it seems that $P^...
Reiner Czerwinski's user avatar
0 votes
1 answer
72 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 ...
Brian's user avatar
  • 1
0 votes
2 answers
41 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 ...
lz9866's user avatar
  • 305
-1 votes
2 answers
59 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$?
ccp's user avatar
  • 1
3 votes
1 answer
113 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 ...
TimD1's user avatar
  • 150
3 votes
3 answers
224 views

Question about the Relativization barrier

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 ...
Reiner Czerwinski's user avatar
1 vote
3 answers
114 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 ...
sharkeater123's user avatar
2 votes
2 answers
155 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?
agimarco's user avatar
1 vote
1 answer
28 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 ...
Tyler's user avatar
  • 11
0 votes
1 answer
44 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 ...
Tim Brown's user avatar
0 votes
1 answer
142 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 ...
tonik's user avatar
  • 195
0 votes
1 answer
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 ...
agemO's user avatar
  • 177
0 votes
4 answers
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 ...
CuriosityScream's user avatar
1 vote
1 answer
55 views

Is ANF-SAT P or NP?

Given a finite set of equations in ANF, for example: $$ \begin{cases} (x_1 \land x_2) \oplus (x_1 \land x_3 \land x_4) \oplus 1 = 0 \\ x_3 \oplus (x_2 \land x_3 \land x_4) = 0 \\ (x_1 \land x_4) \...
Omid's user avatar
  • 13
4 votes
1 answer
64 views

Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?

One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many ...
CuriosityScream's user avatar
0 votes
1 answer
40 views

P vs. NP problem and understanding "worst case complexity"

Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
user918212's user avatar
0 votes
1 answer
61 views

Unpacking the notion of "hardest instances" for NP-complete problems

Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...
user918212's user avatar
0 votes
0 answers
52 views

Could we know what's the total number of unsatisfiable 3SAT formulas for a given n variables?

given some $n$ variables I would be interested to know what is the count of all 3SAT formulas under $n$ that are unsatisfiable. An example of all 3SAT forumlas under $n=3$ is the following: $$ ( x \...
matan Pleblist's user avatar
0 votes
2 answers
63 views

How could NP-complete problems be in P?

I've learned some basics about P and NP. Please excuse if the following is not very precise. I've read that NP-complete problems are the hardest problems in NP. (Is that correct?) But now I'm ...
Gere's user avatar
  • 160
1 vote
0 answers
56 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 (...
infobox's user avatar
  • 11
1 vote
1 answer
61 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 ...
lucasbbs's user avatar
  • 113
3 votes
0 answers
28 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 ...
441Juggler's user avatar
0 votes
0 answers
74 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, ...
Alonso Montero's user avatar
2 votes
2 answers
124 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 ...
Colonizor48's user avatar
2 votes
1 answer
79 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 ...
tricky_labyrinth's user avatar
0 votes
2 answers
130 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 ...
eipim1's user avatar
  • 1
1 vote
1 answer
57 views

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

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
2080's user avatar
  • 191
-2 votes
2 answers
337 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 ...
Colonizor48's user avatar
0 votes
1 answer
67 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 ...
CLEE's user avatar
  • 3

1
2 3 4 5 6