Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

Filter by
Sorted by
Tagged with
53
votes
2answers
7k views

Are there subexponential-time algorithms for NP-complete problems?

Are there NP-complete problems which have proven subexponential-time algorithms? I am asking for the general case inputs, I am not talking about tractable special cases here. By sub-exponential, I ...
34
votes
2answers
4k views

Is there a task that is solvable in polynomial time but not verifiable in polynomial time?

A colleague of mine and I have just hit some notes of one of our professors. The notes state that there are tasks that are possible to solve in polynomial time (are in the class of PF) but that are ...
27
votes
3answers
700 views

NP-complete problems not “obviously” in NP

It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is $\textbf{...
23
votes
4answers
4k views

Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time? Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
22
votes
3answers
2k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
21
votes
2answers
3k views

How is the traveling salesman problem verifiable in polynomial time?

So I understand the idea that the decision problem is defined as Is there a path P such that the cost is lower than C? and you can easily check this is true by verifying a path you receive. ...
16
votes
3answers
658 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
15
votes
4answers
3k views

Proof Complexity of a Proof or Disproof of P = NP

Has there been any research on the proof complexity of a resolution to the P=NP problem? If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that ...
13
votes
3answers
1k views

Can any finite problem be in NP-Complete?

My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ...
13
votes
1answer
1k views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
12
votes
5answers
5k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
12
votes
2answers
3k views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
12
votes
2answers
2k views

Is Post Correspondence Problem in NP?

I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input ...
11
votes
1answer
221 views

Is this NP-hard? I cannot prove it.

I have a problem and I guess it NP-hard, but I cannot prove it. Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest. there are some directed edge between layers, where ...
10
votes
4answers
5k 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. ...
10
votes
1answer
1k views

Intuition behind Relativization

I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will ...
10
votes
1answer
358 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
9
votes
1answer
9k views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
8
votes
2answers
846 views

Is detecting easy instances of NP-hard problems easy?

My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible ...
8
votes
1answer
1k views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
8
votes
1answer
335 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
8
votes
3answers
482 views

Simple interepretation problem regarding Polynomial Hierarchy?

So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for $P^{NP}$ $NP^{NP}$ $coNP^...
8
votes
3answers
206 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
8
votes
1answer
105 views

Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following: $L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$ $L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$ Claim $L_1 \leq_P ...
8
votes
1answer
739 views

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
8
votes
0answers
235 views

Are there consequences for P ≠ NP that are unintuitive?

It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
7
votes
6answers
3k views

Can a subset of an NP-complete problem be in P?

The problem is NP-complete (proven) for all input data (without exception). We assume that P != NP. Is it possible that there is an (infinitely large) subset of the problem, for which this subset is ...
7
votes
4answers
531 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
7
votes
4answers
11k views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
7
votes
2answers
1k views

An one-sentence proof of P ⊆ NP

Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence: It is trivial to show that $\mathbf{P} \...
7
votes
1answer
556 views

How do we know any problem is in NP-complete if we don't know all problems in NP?

A problem is NP-complete if: It is in NP. All problems in NP can reduce to it. It's number 2 that I'm concerned with here. I would be highly surprised if we knew every problem in NP. Based on that ...
7
votes
1answer
1k views

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this : https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg I wonder if ...
7
votes
2answers
2k views

A “natural” decidable problem not in $\mathsf{NP}$? [duplicate]

Are there any "natural" examples of decidable problems that are definitively known not to be in NP? The decidable languages I know of that are not contained in NP are usually derived from the time ...
7
votes
1answer
1k views

How can I show that the Cook-Levin theorem does not relativize?

The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) : Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not ...
7
votes
2answers
1k views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
7
votes
1answer
63 views

Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP ...
7
votes
1answer
6k views

NP $\subsetneq$ EXP?

I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book ...
7
votes
1answer
361 views

Can proofs-of-work be probabilistically checkable?

I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site. ...
7
votes
1answer
368 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
7
votes
2answers
900 views

Polytime algorithm for SUBSET-SUM assuming P=NP

In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in ...
6
votes
2answers
2k views

Give one example where it takes Non- deterministically exponential time to solve the problem?

I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the ...
6
votes
1answer
7k views

Does every problem in NP have an exponential time algorithm?

I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.
6
votes
1answer
172 views

Why doesn't a time cutoff convert NP problems into co-NP? [duplicate]

Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations. You make a tweak to the verifier program, so that if it takes more than $f(n)$ ...
6
votes
1answer
493 views

Why can't we exploite finiteness to prove incompleteness in NP?

It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not ...
6
votes
2answers
77 views

Sequence to explore the complexity of the NP problem

Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? ...
6
votes
1answer
147 views

Are there any known lower-bounds for complexity on Non-determinsitic machines

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time. Are they any problems where we have known lower bounds for ...
6
votes
1answer
884 views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
6
votes
1answer
639 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...
6
votes
1answer
69 views

Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Assuming $\Sigma = \{ 0, 1\}$.. Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$? So it ...
6
votes
1answer
412 views

How to prove that finding math proofs is $\text{NP}$-hard?

This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak. Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a finite ...

1
2 3 4 5
10