# Questions tagged [decision-problem]

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

57 questions
Filter by
Sorted by
Tagged with
8k views

551 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 ...
4k 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 ...
2k views

### Proof that whether a regular language is finite is decidable [duplicate]

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
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.
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 ...
4k views

### Why are Chess, Mario, and Go not NP-complete?

I have a hole in my understanding of what makes a problem NP. I understand that Mario, for example, is NP-hard - it can be reduced to the NP-complete problem of 3SAT (see https://www.youtube.com/...
2k views

301 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 ...
832 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-...
3k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
545 views

### When is splitting a collection coins two ways NP-complete?

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ...
116 views

### Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
419 views

### How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
573 views

### Is equivalence of a CFG and an RG undecidable?

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?
447 views

### Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
55 views

### A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
1k views

### Decision version of the traveling salesman problem and NP-hardness

Wikipedia says: The problem has been shown to be NP-hard and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-...
1k views

### Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
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 ...
1k views

264 views

### Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?

I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard. Is deciding if there's a solution to a single ...
464 views

### Do all algorithms aim to solve decision problems?

An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more ...
68 views

### Is there a generic procedure to produce (hard enough) decision problems?

This comment by @DerekElkins suggests a general method of constructing decision problems for problems with bit-strings as output, of which a slightly formalised version is the following: Given a ...
1k views

### Reduction: Vertex Cover to Binary Integer Program (Decision Problem)

I am stuck with the following task: Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming". I have the feeling that there must ...
483 views

### Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
513 views

### Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
35 views

### Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

$\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly ...
700 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 ...
2k views

### Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
243 views

### How does the problem of having a coffee-machine close relate to vertex cover?

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that ...
948 views

### What is a Turing Machine in class coNP

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
211 views

### Feasibility of linear inequalities with binary variables

I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
36 views

### Decision problems with complex input validation

In an answer to a question regarding input validation in decision problems, @Apass Jack wrote It is easy to check whether a problem instance is a valid instance or not for almost all decision ...