# Questions tagged [decision-problem]

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

414 questions
Filter by
Sorted by
Tagged with
5k 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/...
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.
117 views

### How could I prove that $B$ reduces to $A$ in polynomial time in this case?

Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time? Thanks in advance.
184 views

### Why do i have to show that a problem L $\in$ NP before i start a polynomial reduction?

i want to do a polynomial reduction from the Independent-Set-Problem which is NP-complete to the AUCTION-Problem, to show that AUCTION $\in$ NP-complete, but why do i always have to show first, that ...
138 views

### Common expression language for users [closed]

for my current project I am working with decision tables that uses expression to determine conditions. Currently the decision tables support FEEL expressions. A simple example table using feel ...
84 views

### Deciding whether a CFG is parity absent

Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ ...
161 views

### Rice theorem to prove Emptiness problem

Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable? With the emptiness problem I mean the question if a certain machine doens't accept any input ? If you ...
332 views

### How many decision problems do exist?

Are there countable infinte decision problems or uncountable infinite? Thank you
306 views

### Reducing a problem with two knapsack that needs equal number of items from Knapsack?

I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
302 views

### decision tree redundancy optimization

First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy. the following is an example of optimization: ...
244 views

### Complexity class (P/NP) variants of Hamiltonian paths problems

I know that the following problems related to Hamiltonian paths in graph are NP-complete: Undirected Hamiltonian circuit: Given an undirected graph, does it has a cycle that passes through each node ...
2k 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 ...
1k views

### Reduction from Vertex Cover

The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of ...
191 views

### How the closure properties of the formal languages dictate decidability of their problem

Consider the following problem: Is $L_1 * L_2$ is of $LType$? where we know that both $L_1$ and $L_2$ are of type $LType$ and $LType$ is closed under $*$ operation. Above, by $LType$, I mean any ...
226 views

66 views

### Checking membership in DFA with fixed length using AC1 circuit?

I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
291 views

### How to prove that a language $A$ is decidable?

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering. Word length alphabetically means a sorting first ...
96 views

### Does every procedure have a structural equivalent?

Suppose I have a basic mathematical function like: $f(x) = x^2 + 2$ implemented in typed pseudo-code as: int f(x) { return x*x + 2; } If we were to break ...
619 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 ...
145 views

### Implications of Pessiland [closed]

Consider 3COL (three colourability), Travelling Salesman, 3SAT and 2SAT. Which of these problems can be solved in polynomial time if we happen to live in world 3 (Pessiland). My Thinking - We know ...
4k views

### The importance of the membership problem

Given a word $w$ and a language $L$, we want to check if $w\in L$. This is called the membership problem. Why is the membership problem important?
1k views

### The language of Turing machines that accept exactly $k$ inputs

For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X_k$ ...
595 views

### How do you know a problems is non-computable?

I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which ...
1k views

### Can the decision version of an optimization problem in NP, be in P?

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore ...
709 views

### show that special case of NP-complete problem is also NP-complete?

I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure ...
166 views

### Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem: PARTITION Input: A list of positive integers $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
3k 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 ...