The tag has no usage guidance.

learn more… | top users | synonyms

-1
votes
1answer
31 views

What does permanent in poly time over $\Bbb F_p$ give?

A paper on arXiv [1] states in abstract that permanent of an $n\times n$ matrix over $\Bbb F_p$ in polynomial time gives $NP=RP$. My query is why is 'permanent of an $n\times n$ matrix over $\Bbb ...
1
vote
0answers
83 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have ...
0
votes
0answers
71 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesmen problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorther (Yes/No) Now assume $P \neq NP$: Since ...
4
votes
0answers
49 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 ...
17
votes
5answers
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
36 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 ...
3
votes
1answer
109 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
33 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
83 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
44 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
40 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 ...
7
votes
2answers
330 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
71 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
33 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
1k 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
202 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
180 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
259 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 ...
8
votes
0answers
112 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 ...
11
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
29 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
188 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
739 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
143 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
73 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
85 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
111 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
213 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 ...
47
votes
9answers
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
865 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
134 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
79 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
404 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 ...
7
votes
1answer
199 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
205 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
106 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
101 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 ...
4
votes
2answers
107 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm is based on the idea that by observing a quantum state, one has to ...
1
vote
1answer
68 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
228 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
185 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
113 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 ...
-2
votes
1answer
811 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
130 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, ...