Skip to main content

Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
330 votes
7 answers
160k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
Mirrana's user avatar
  • 4,319
128 votes
6 answers
16k views

Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. ...
Ken Li's user avatar
  • 3,088
106 votes
5 answers
18k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
Raphael's user avatar
  • 72.6k
86 votes
6 answers
22k views

How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
user avatar
69 votes
3 answers
33k views

Knapsack problem -- NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
Strin's user avatar
  • 1,505
65 votes
7 answers
15k views

Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
Gaslight Deceive Subvert's user avatar
65 votes
9 answers
13k 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 ...
RLH's user avatar
  • 829
65 votes
2 answers
11k 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 ...
ksb's user avatar
  • 781
64 votes
8 answers
5k views

Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
Khanzor's user avatar
  • 1,451
63 votes
6 answers
26k views

If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, ...
pafnuti's user avatar
  • 729
56 votes
4 answers
9k views

Why polynomial time is called "efficient"?

Why in computer science any complexity which is at most polynomial is considered efficient? For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
Ran G.'s user avatar
  • 20.7k
54 votes
6 answers
15k views

Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
racc44's user avatar
  • 657
54 votes
3 answers
14k views

Why did Google not use an NP problem for their quantum supremacy experiment?

Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and ...
Vincent's user avatar
  • 723
50 votes
2 answers
9k views

What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
Joey Eremondi's user avatar
47 votes
12 answers
12k views

Can a computer determine whether a mathematical statement is true or not?

I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting: During the first half of the twentieth century, mathematicians such as ...
Arsalan MGR's user avatar
45 votes
4 answers
20k views

What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
Raphael's user avatar
  • 72.6k
44 votes
4 answers
37k views

Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
vpiTriumph's user avatar
42 votes
2 answers
14k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
user25876's user avatar
  • 423
41 votes
3 answers
6k views

Decision problems vs "real" problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
Ran G.'s user avatar
  • 20.7k
40 votes
4 answers
24k views

Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
Sasha the Noob's user avatar
40 votes
7 answers
4k views

Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity. In practice, what is ...
Kaveh's user avatar
  • 22.3k
39 votes
5 answers
29k views

How can I verify a solution to Travelling Salesman Problem in polynomial time?

So, TSP (Travelling salesman problem) decision problem is NP complete. But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is ...
Lazer's user avatar
  • 1,087
38 votes
2 answers
20k views

How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
Anonymous's user avatar
  • 381
38 votes
4 answers
25k views

Generalised 3SUM (k-SUM) problem?

The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$. It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$....
bitmask's user avatar
  • 1,755
38 votes
1 answer
2k views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
Chao Xu's user avatar
  • 3,083
37 votes
4 answers
15k views

Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?
Barte's user avatar
  • 503
35 votes
3 answers
4k views

Why is Relativization a barrier?

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to ...
Nikhil's user avatar
  • 619
35 votes
2 answers
6k views

NP-Hard problems that are not in NP but decidable

I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable? For example, the halting problem is NP-Hard, not NP-Complete, but is ...
oneself's user avatar
  • 453
34 votes
2 answers
5k 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 ...
Drozi's user avatar
  • 341
33 votes
2 answers
14k views

Optimization version of decision problems

It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem optimization/search version: Given an undirected unweighted graph $G ...
user avatar
32 votes
2 answers
3k views

Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
zyl1024's user avatar
  • 462
31 votes
1 answer
11k views

Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
Kevin Kibler's user avatar
31 votes
3 answers
10k views

Teaching NP-completeness - Turing reductions vs Karp reductions

I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions? I feel that the ...
D.W.'s user avatar
  • 162k
31 votes
5 answers
14k views

"NP-complete" optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
Aniket Schneider's user avatar
30 votes
3 answers
1k views

Measuring the difficulty of SAT instances

Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance. One way is to run existing solvers, but that kind of defeats the purpose of estimating ...
Artem Kaznatcheev's user avatar
30 votes
5 answers
62k views

How can I reduce Subset Sum to Partition?

Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation! Is it possible to reduce this problem ...
dbonadiman's user avatar
30 votes
1 answer
13k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
hugomg's user avatar
  • 1,379
30 votes
1 answer
2k views

Is regex golf NP-Complete?

As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ...
Steven Stadnicki's user avatar
30 votes
1 answer
993 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
Mohammad Al-Turkistany's user avatar
29 votes
3 answers
4k views

Are there any problems that are easy to compute but hard to verify?

Assuming P $\neq$ NP, NP-complete problems are "hard to solve, but have answers that are easy to check." Does it make any sense to consider the opposite, that is, problems for which it's easy to ...
rphv's user avatar
  • 1,624
29 votes
1 answer
20k views

Is the k-clique problem NP-complete?

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete: Cliques have also been ...
user avatar
29 votes
1 answer
744 views

Subset Sum problem with many divisibility conditions

How does the computational complexity of the Subset Sum problem depend on the parameter $\alpha(S)$ of the input $(S, t)$, defined as follows? Considering $S$ under the divisibility partial order, i.e....
Chao Xu's user avatar
  • 3,083
29 votes
2 answers
2k views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
Sekti's user avatar
  • 393
28 votes
4 answers
6k views

Why is SAT so important in theoretical computer science?

In my Computability and Complexity class, we are focusing on P, NP, NP-complete, and NP-hard problems and the one thing that keeps coming up is the SAT problem, in the context of reduction from one ...
Rishav's user avatar
  • 391
28 votes
2 answers
11k views

Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
Vitaly Olegovitch's user avatar
27 votes
5 answers
14k views

Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
BlueRaja - Danny Pflughoeft's user avatar
27 votes
5 answers
18k views

What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]

In many textbooks NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic ...
user5507's user avatar
  • 2,191
27 votes
3 answers
9k views

Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
hsalin's user avatar
  • 733
27 votes
3 answers
846 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{...
gardenhead's user avatar
  • 2,230
26 votes
2 answers
2k views

Is Dominosa NP-Hard?

Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are ...
Yoav bar sinai's user avatar

1
2 3 4 5
110