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 ...
68 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D,Ā Ī”} |Ā D is aĀ DFAĀ and P is aĀ Ī”DAĀ whichĀ L(D) ā© L(Ī”) = ā } Here what I think I give a reduction from E(TM). I suppose that this ...