Questions tagged [decision-problem]

A question in some formal system with a yes-or-no answer.

Filter by
Sorted by
Tagged with
64
votes
7answers
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 ...
28
votes
2answers
9k 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 ...
25
votes
5answers
11k 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 ...
25
votes
1answer
4k views

Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

Those terminologies confuse me. As I understand SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search). Decision procedure is a procedure to decide the ...
22
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. ...
21
votes
4answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
18
votes
3answers
3k views

Why there are no approximation algorithms for SAT and other decision problems?

I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the ...
18
votes
0answers
383 views

Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
16
votes
2answers
1k views

What is the difference between “Decision” and “Verification” in complexity theory?

In Michael Sipser's Theory of Computation on page 270 he writes: P = the class of languages for which membership can be decided quickly. NP = the class of languages for which membership can be ...
14
votes
2answers
582 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 ...
13
votes
3answers
1k views

Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
13
votes
0answers
593 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
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 ...
12
votes
2answers
3k views

Is the equality of two DFAs a decidable problem?

So given two DFAs, is the problem of finding if they generate the same language a Decidable problem? I already know that Equality of two CFL is not Decidable but what about Equality of two DFAs? ...
12
votes
3answers
2k views

Is there an efficient test for if an NFA accepts a subset of another NFA?

So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is ...
11
votes
1answer
1k views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
11
votes
3answers
564 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 ...
11
votes
2answers
150 views

An $\mathbb F$-algebra as input to an algorithm

I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with ...
11
votes
2answers
476 views

Longest cycle contained in two cycles

Is the following problem NP-complete? (I assume yes). Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a ...
10
votes
3answers
9k views

All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

My book states this If a decision problem B is in P and A reduces to B, then decision problem A is in P. A decision problem B is NP-complete if B is in NP and for every problem in A in ...
10
votes
3answers
583 views

$2k$ number assignment

Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ ...
10
votes
1answer
438 views

Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. ...
9
votes
3answers
3k views

Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
9
votes
3answers
5k 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 ...
9
votes
1answer
4k views

Is the 0-1 Knapsack problem where value equals weight NP-complete?

I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-...
9
votes
2answers
388 views

Complexity of a subset sum variant

Is this variant of the subset sum problem easy/known? Given an integer $m$, and a set of positive integers $A = \{x_1, x_2, ..., x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = ...
9
votes
1answer
875 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
1answer
356 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
2answers
1k views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
8
votes
1answer
113 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
990 views

Complexity of (SAT to 3-SAT) Problem?

It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible (...
8
votes
1answer
386 views

Is the universe problem for one-counter automata with restricted alphabet size undecidable?

Consider the following universe problem. The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$. In [1], it ...
8
votes
2answers
2k views

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space. But what about PDAs with $\...
7
votes
2answers
937 views

3-SAT where variables occur equally many times as a positive literal and as a negative literal

Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$. Is it NP-...
7
votes
3answers
909 views

Does every computational problem have a decision version?

Is the following claim correct?: Every computational problem has a decision version of roughly equal computational difficulty. If the above claim is correct, please give a reference for it. (I ...
7
votes
3answers
2k views

Computer science problems related to music?

Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
7
votes
3answers
988 views

Undecidability of telling if a program returns true or false

Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are ...
7
votes
2answers
356 views

primitive recursive functional equivalence

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many ...
7
votes
1answer
879 views

Is Post's Correspondence Problem decidable with fixed word size?

So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$. I'm wondering, can anything similar be said for when there is a fixed word length? To be precise, here's ...
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
874 views

Algorithms that run in polynomial time if P=NP

On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
7
votes
1answer
597 views

Complexity of Monotone (+,2) SAT problem?

To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem: Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF ...
7
votes
1answer
2k views

NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension. Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
7
votes
1answer
863 views

Understanding of Turing's Answer to the Entscheidungsproblem

I apologize if this question has been asked before, but I was not able to find a duplicate. I have just finished reading The Annotated Turing and I am a bit confused. From what I understand, the ...
7
votes
1answer
251 views

sequence of problems that take $\Theta(n^k)$ for increasing $k$?

Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly? Suppose for example that we would ...
6
votes
2answers
620 views

Reconciling NP and the decision problem

So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the ...
6
votes
3answers
1k views

How many decidable decision problems are there?

Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?
6
votes
1answer
259 views

Complexity of deciding the satisfiability of a quasi-monotone CNF formula

A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal). What is the complexity of deciding its ...
6
votes
1answer
285 views

What complexity class does this variation of traveling salesman problem belong to?

Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers. ...
6
votes
2answers
600 views

Are there any proofs of exponential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...

1
2 3 4 5
9