The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
0answers
40 views

Is anything known about the structure of sets of valuations representable by 3CNF formulas?

Let's suppose we have propositional variables $x_1 ... x_n$. A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$. So, there are $2^n$ possible ...
15
votes
4answers
3k views

Would proving P≠NP be harder than proving P=NP?

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP. Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove ...
0
votes
0answers
34 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in ...
2
votes
1answer
83 views

Stronger versions of P != NP which better express actual convictions

Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy ...
-1
votes
1answer
31 views

3SAT with an oracle for expanding the clauses

Let's consider 3SAT, so we have clauses like: (A or B or C) and (A or not B or D) and ... If we distribute the "and" over the first two clauses, we get the disjunction of: ...
-2
votes
2answers
66 views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
0
votes
0answers
43 views

If EXP = NEXP, can we say anything about P and NP? [duplicate]

I found one older question asked about this but without any responses.
4
votes
1answer
32 views

Logarithmic Randomness is Necessary for PCP Theorem

I am trying to proof the following statement: If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$. Here are my ideas for the proof: It can be easily worked ...
6
votes
2answers
263 views

How to prove P$\neq$NP?

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point. We can show that P $=$ NP if and only if we can design an algorithm that solves any ...
-2
votes
1answer
64 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
0
votes
1answer
31 views

Does classification of a problem also require the algorithm used? [duplicate]

Just learnt that a problem in computer science can be divided into the following categories Polynomial problems NP problems NP hard problems NP complete problems ...
2
votes
1answer
27 views

Schaefer's dichotomy theorem and reformulating 3-literal clauses

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would ...
4
votes
3answers
727 views

Evolving artificial neural networks for solving NP problems

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. ...
1
vote
2answers
178 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 ...
3
votes
2answers
163 views

Is my theorem about $P \neq NP$ correct? [closed]

It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from ...
1
vote
2answers
178 views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
4
votes
1answer
49 views

Constructing languages in NPI other than through Ladner's Theorem

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse ...
7
votes
0answers
99 views

P vs NP and the Time Hierarchy

Assuming P $\neq$ NP, is it possible that there exists a $k$ such that for all $j$, $\textsf{DTIME}(t^j) \subseteq \textsf{NTIME}(t^k)$? There reason I ask is that I assume P = NP implies that for ...
10
votes
1answer
1k views

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ...
0
votes
0answers
27 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
4
votes
3answers
163 views

Could an NP-hard problem have a mechanical or physical solution method?

Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we ...
0
votes
0answers
20 views

Place 4 notorious problems into 2 diagrams (one assuming P=NP, and the other one assuming P!=NP) [duplicate]

This diagram is on Wikipedia: On left side we see NP-hard intersecting NP class (assuming P!=NP), on right side we see NP-hard including NP (assuming P=NP) Where should I place the following ...
7
votes
2answers
726 views

Why does Schaefer's theorem not prove that P=NP?

This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P ...
2
votes
1answer
104 views

$P \neq NP$ and determinism

Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine ...
5
votes
1answer
132 views

Does $P \neq NP$ imply $NP \neq PSPACE$?

Is it true that $\mathsf{P} \neq \mathsf{NP}$ implies $\mathsf{NP} \neq \mathsf{PSPACE}$? I have here some problem that is in $\mathsf{PSPACE} \setminus \mathsf{NP}$ if $\mathsf{P} \neq \mathsf{NP}$. ...
1
vote
0answers
72 views

A paper argumenting that P might be equal to NP [closed]

It seems like most serious computer scientists believe that P is not equal to NP, but they just do not know how to prove it. Is there any worth-mentioning paper in which an argument is made in favor ...
1
vote
1answer
77 views

If P is equal to NP, then what happens to the problems those can be solved in polynomial time?

Suppose that an algorithm $A$ is able to solve a problem in NP in polynomial time. Does this effect the good old sorting, searching, shortest path, minimum spanning tree etc. algorithms? Can this ...
2
votes
3answers
94 views

Could an NP-Hard problem be in P in after a basis transform? [closed]

I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked. So here goes: Take the following problem for example: Let ...
11
votes
1answer
190 views

Why is this argument for $P\neq NP$ wrong?

I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some ...
41
votes
10answers
5k views

What would be the real-world implications of a constructive $P=NP$ proof?

I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems ...
2
votes
1answer
575 views

If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
5
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
2
votes
1answer
113 views

Can oracle arguments separate P and NP?

I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP. However, if there is an oracle language $A \in \textbf{P}$ such that ...
2
votes
1answer
69 views

What is the implication of the sentence: “if any NP complete problem is p time solvable, then all problems in NP are p time solvable”

I find this quote here on page 13 Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p ...
1
vote
1answer
352 views

Subset sum algorithm in O(n³ log n)?

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ...
6
votes
1answer
182 views

If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the ...
2
votes
1answer
152 views

Homomorphism erasing information

I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ...
0
votes
1answer
99 views

Problem with my proof that NP = coNP?

Is there a problem with this proof that NP = coNP? It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The ...
1
vote
1answer
92 views

What are the current known implications of the complexity of Integer Factorization?

According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other ...
1
vote
1answer
59 views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ ...
3
votes
2answers
221 views

Does this mean $P = NP$

I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 ...
1
vote
2answers
178 views

If P != NP, then 3-SAT is not in P

I hope I'm in the right section: I know that if P = NP, then 3-SAT can be solved in P (Cook), but is the opposite valid, too? If P != NP, then 3-SAT is not in P? Thanks!
0
votes
0answers
28 views

Can P vs NP be independent of accepted axioms? [duplicate]

On wikipedia's page on P vs NP it says that think that of 151 researchers surveyed, their thoughts were as follows: "126 (83%) believed the answer to be no, 12 (9%) believed the answer is yes, 5 ...
5
votes
0answers
109 views

research on OR and AND compression in SAT formulas [closed]

this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far. A simple proof that AND-compression of NP-complete ...
-3
votes
1answer
772 views

If I solve hard instance, therefore I prove NP=P? [duplicate]

If someone (off-topic) asks a question (on-topic) like this: Suppose that he claims that $\mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that ...
-1
votes
1answer
123 views

what are the basic/typical/common mistakes in P=NP claims? [duplicate]

the P vs NP problem attracts a lot of attention, not all of it desirable, for a wide variety of reasons. there are many P=NP claims eg on this widely cited list maintained by mathematician Woegeorgi, ...
0
votes
0answers
83 views

Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? [closed]

I am trying to either prove or refute the claim mentioned in the title. Any ideas ?
11
votes
1answer
293 views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
4
votes
2answers
199 views

Is this language depending on P = NP recursive?

Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language $$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$ ...
0
votes
1answer
395 views

What makes it so difficult to prove P =/≠ NP? — The subset sum issue [closed]

I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to ...