Skip to main content
Computer Science

Questions tagged [np]

Ask Question

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

797 questions
Newest Active Bountied Unanswered
67 votes
2 answers
11k views

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 ...
ksb's user avatar
  • 801
35 votes
2 answers
5k views

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 ...
Drozi's user avatar
  • 351
27 votes
3 answers
977 views

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{...
gardenhead's user avatar
  • 2,250
26 votes
13 answers
7k views

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
proof-of-correctness's user avatar
  • 582
24 votes
3 answers
2k views

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 ...
GregRos's user avatar
  • 525
23 votes
5 answers
6k views

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 ...
donkey's user avatar
  • 352
23 votes
2 answers
4k views

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. ...
wjmccann's user avatar
  • 579
19 votes
2 answers
4k views

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
user avatar
17 votes
4 answers
3k views

The decision version of the problem Integar Linear Programming is the following: Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$. Question: is there a ...
Nathaniel's user avatar
  • 18.7k
17 votes
1 answer
24k views

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
Hrishikesh's user avatar
  • 171
16 votes
2 answers
2k views

This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
shivams's user avatar
  • 261
16 votes
3 answers
1k views

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 ...
user6818's user avatar
  • 1,175
15 votes
4 answers
3k views

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 ...
Tony Johnson's user avatar
  • 153
15 votes
5 answers
8k views

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 ...
simpleton's user avatar
  • 181
15 votes
4 answers
3k views

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 ...
TheRapture87's user avatar
  • 271

15 30 50 per page
1
2 3 4 5
…
54