Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
326 votes
7 answers
158k 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,259
45 votes
4 answers
19k 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.3k
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
37 votes
2 answers
18k 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
  • 371
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
24 votes
2 answers
4k views

Reduce the following problem to SAT

Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \...
Aden Dong's user avatar
  • 1,131
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
65 votes
2 answers
10k 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
40 votes
3 answers
5k 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
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.2k
25 votes
7 answers
6k views

Justification for neglecting constant factors in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
gpuguy's user avatar
  • 1,799
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
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.3k
30 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
14 votes
5 answers
7k 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 ...
simpleton's user avatar
  • 171
13 votes
3 answers
2k views

Why can't we flip the answer of a NDTM efficiently?

I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) ...
user1494080's user avatar
5 votes
4 answers
2k views

Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

In the paper "PRIMES is in P" the following is said (page 1): Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is ...
M Smith's user avatar
  • 467
127 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,078
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
30 votes
1 answer
12k 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
16 votes
2 answers
4k views

Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression? In other words, is there another ...
Jason's user avatar
  • 171
25 votes
3 answers
2k views

Is there a sometimes-efficient algorithm to solve #SAT?

Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables. I would like to count the number of satisfying assignments for $B$. That is, I want to find the ...
Mark Dominus's user avatar
  • 1,537
20 votes
2 answers
5k views

Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
user2145167's user avatar
16 votes
1 answer
2k views

Universal simulation of Turing machines

Let $f$ be a fixed time-constructable function. The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given the description of ...
Kaveh's user avatar
  • 22.2k
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
24 votes
5 answers
4k views

P-Completeness and Parallel Computation

I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is ...
Dave Clarke's user avatar
  • 20.2k
15 votes
2 answers
1k views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
Raphael's user avatar
  • 72.3k
7 votes
2 answers
24k views

How to prove NP-hardness of a longest-path problem?

I have this question: ...
omega's user avatar
  • 553
7 votes
1 answer
5k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
Yechiel Labunskiy's user avatar
4 votes
1 answer
8k views

Complexity of multiplication

I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being ...
Duke of Sam's user avatar
3 votes
1 answer
2k views

Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set ...
user2566092's user avatar
  • 1,721
69 votes
3 answers
32k 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
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
38 votes
4 answers
24k 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
30 votes
3 answers
9k 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
  • 158k
29 votes
5 answers
60k 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
21 votes
3 answers
10k views

If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete. Why these two languages in particular? Can't we reduce any other ...
David Faux's user avatar
  • 1,597
20 votes
2 answers
559 views

How to scale down parallel complexity results to constantly many cores?

I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC: NC is the class of problems that can be solved by a ...
Raphael's user avatar
  • 72.3k
16 votes
3 answers
9k views

Prove NP-completeness of deciding satisfiability of monotone boolean formula

I am trying to solve this problem and I am really struggling. A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example, $\qquad (x_1 \lor x_2) ...
nat's user avatar
  • 163
15 votes
2 answers
1k views

Decision problems in $\mathsf{P}$ without fast algorithms

What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known ...
Juho's user avatar
  • 22.5k
15 votes
2 answers
19k views

algorithm time analysis "input size" vs "input elements"

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
Jesus Salas's user avatar
13 votes
2 answers
728 views

Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
hyperpallium's user avatar
10 votes
2 answers
8k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
accounted4's user avatar
3 votes
1 answer
4k views

Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD

I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-...
rollotommasi's user avatar
38 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,077
34 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
  • 609
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
27 votes
3 answers
8k 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
13 votes
2 answers
2k views

Decidable restrictions of the Post Correspondence Problem

The Post Correspondence Problem (PCP) is undecidable. The bounded version of the PCP is $\mathrm{NP}$-complete and the marked version of the PCP (the words of one of the two lists are required to ...
Vor's user avatar
  • 12.5k
13 votes
1 answer
1k views

Why are all problems in FPTAS also in FPT?

According to the Wikipedia article on polynomial-time approximation schemes: All problems in FPTAS are fixed-parameter tractable. This result surprises me - these classes seem to be totally ...
templatetypedef's user avatar

1
2 3 4 5
13