Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

67
votes
5answers
16k views

In basic terms, 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 ...
24
votes
3answers
866 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. ...
18
votes
4answers
702 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 ...
32
votes
6answers
2k 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 ...
13
votes
1answer
1k 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. ...
45
votes
5answers
7k 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 ...
16
votes
2answers
1k 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 ...
12
votes
1answer
613 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 ...
19
votes
1answer
4k 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, ...
22
votes
2answers
2k 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 ...
44
votes
7answers
2k views

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 ...
56
votes
5answers
2k 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. ...
12
votes
2answers
506 views

Finding reductions

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 ...
11
votes
2answers
617 views

A polynomial reduction from any NP-complete problem to bounded PCP

Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
18
votes
2answers
813 views

NP-Hard that is not NP-Complete and not Undecidable

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 ...
15
votes
1answer
362 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 ...
8
votes
1answer
549 views

Types of reductions and associated definitions of hardness

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
10
votes
2answers
427 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 ...
10
votes
1answer
2k 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 ...
10
votes
2answers
529 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 ...
13
votes
2answers
272 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 ...
6
votes
4answers
436 views

Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists. Is there a good / quick / easy way to see ...
-2
votes
1answer
56 views

NP hard: Mixed Q Horn SAT

Prove that Mixed Quantified Horn SAT problem is NP hard by reducing the Q3SAT problem to it. Q3SAT: 3SAT with possibly universally and existentially quantified variables. Mixed Quantified Horn ...
14
votes
4answers
3k 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 ...
18
votes
3answers
4k 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 ...
14
votes
1answer
418 views

Proving the (in)tractability of this Nth prime recurrence

As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
13
votes
4answers
4k 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 ...
10
votes
3answers
653 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 ...
19
votes
1answer
306 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 ...
10
votes
2answers
276 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 ...
5
votes
0answers
85 views

research on OR and AND compression in SAT formulas

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 ...
10
votes
2answers
304 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 ...
7
votes
5answers
265 views

Justification for neglecting constants 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 ...
5
votes
1answer
562 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) ...
4
votes
3answers
335 views

Does our PC work as Turing Machine?

Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
15
votes
4answers
359 views

Showing that a problem in X is not X-Complete

The Existential Theory of the Reals is in PSPACE, but I don't know whether it is PSPACE-Complete. If I believe that it is not the case, how could I prove it? More generally, given a problem in some ...
8
votes
1answer
212 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 ...
6
votes
3answers
2k 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 ...
4
votes
3answers
251 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) ...
4
votes
1answer
801 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 ...
3
votes
1answer
113 views

Provability of NP /= P?

I'm a novice to the topic of provability so bear with me... During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an ...
3
votes
1answer
188 views

Can we read N numbers in O(N) time?

In a different post it came up that (using the Turing machine model of computation), it is not even safe to say that $N$ numbers can be read in $O(N)$ time. To me this is boggling since it's ...
2
votes
1answer
228 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, ...
1
vote
1answer
278 views

Using software to calculate the complexity of an algorithm

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
1
vote
1answer
570 views
0
votes
2answers
366 views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
11
votes
2answers
2k views

HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let ...
10
votes
3answers
272 views

Is it possible to decide if a given algorithm is asymptotically optimal?

Is there an algorithm for the following problem: Given a Turing machine $M_1$ that decides a language $L$, Is there a Turing machine $M_2$ deciding $L$ such that $t_2(n) = o(t_1(n))$? The ...
9
votes
1answer
312 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 ...
5
votes
1answer
93 views

Complexity of space density and sequentiality

I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms. When we measure algorithms we tend to give the big-Oh notation ...