Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
5
votes
3answers
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/...
0
votes
1answer
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.
1
vote
1answer
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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$ ...
1
vote
0answers
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 ...
1
vote
1answer
332 views

How many decision problems do exist?

Are there countable infinte decision problems or uncountable infinite? Thank you
1
vote
0answers
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 ...
2
votes
1answer
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: ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
2answers
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 ...
3
votes
1answer
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 ...
1
vote
0answers
226 views

Decision problem 3SAT and Bip[3-1]

Consider the decision problem Bip[3–1], define as follows: Instance: $G = (S,T;E)$, bipartite graph, with $d_G(s) = 3$ for all $s \in S$. Question: Does there exist $S' ⊆ S$ such that in $H = [S'∪T]...
2
votes
2answers
2k 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-...
1
vote
1answer
288 views

MAX SAT Optimization problem

search problem: find the assignment that maximize the number of satisfied clauses For decision problem: determine whether there is an assignment that satisfies k of clauses. optimization problem : ...
1
vote
1answer
274 views

Determine whether a TM visits each of its states exactly once during computation

(Decidable or not?) Formulate the following problem as a language: Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation ...
3
votes
0answers
100 views

Proving NP Completeness [closed]

Given $m$ shortest paths between any two vertices of a graph. Determining whether we can pick $k$ shortest paths such that their union covers all edges. I am trying to reduce set cover problem to it. ...
1
vote
2answers
987 views

Decidability of the language of DFAs accepting only odd-length strings [closed]

Let $L$ be the language $\{\langle M \rangle : M\text{ is a DFA that accepts only odd-length strings}\}$. Prove that $L$ is decidable. How wrong is my answer? Create a TM $T$ that decides $L$: ...
3
votes
2answers
1k views

How do you know if a language accepted by a DFA is $Σ^*$?

I know that a language that is input into a DFA (call it $X$) is regular just by being accepted by it, but given that it is accepted, how can one figure out that $L = Σ^*$? In other words, what does a ...
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 ...
2
votes
1answer
45 views

Decidability algorithm, whether substring belongs to L

It isn't very hard to decide if word belongs to language L. CYK algorithm should do here. Occured thought, can CYK be modified to detect if all words of language L contain some specific subword?
0
votes
1answer
178 views

Is the MinMax/optimization/search variant of a decision problem always easier/equal?

Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant? From Wikipedia: If the longest path ...
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 ...
1
vote
1answer
41 views

Recognizing vs Deciding in defining class BPP

In Sipser's text, he writes: When a probabilistic Turning machine recognizes a language, it must accept all strings in the language and reject all strings not in the language as usual, except ...
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?
-1
votes
2answers
140 views

Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

One of my friends works for a big oil rafinery. He's in charge of optimising the inputs (volumes, maximum price to pay for crude oil etc.) given a profit. He's telling me there are heuristic ways to ...
2
votes
2answers
587 views

Do problems in P have a minimum number of YES and NO instances?

If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an ...
0
votes
0answers
11 views

Is maximising (or minimising) something enough to say that I am solving a decision problem? [duplicate]

We know that every optimisation problem has an equivalent decision problem. So say I keep going up a mountain (I.e. I am maximising my altitude) following a certain number of finite steps (similarly ...
3
votes
3answers
153 views

Why we cannot prove that a computable function is total?

We know that we cannot find an algorithm that would prove that a computable function "f" is total if it IS total. How come? When a function is total, it must have a proof (derived from soundness and ...
2
votes
1answer
283 views

Reduce the following decision problem to CNF-SAT

Input: $X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$} $Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$} $k$, where, $k$ $\leq$ $m$ Output (Yes/No): Satisfying the following condition, can all the elements in set $X$ be ...
1
vote
1answer
453 views

Is this language semi-decidable?

Let $M_w$ be the DTM encoded by the binary string $w$ and let $$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$ I've already proved that this language is undecidable (the ...
3
votes
2answers
58 views

Using oracle machine to speed up tree solution search

Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for ...
0
votes
1answer
2k views

What is the fastest way to check if an integer is divisible by another?

What would the Big O be? Can something like this be done in O(log(n)) where n is the number of bits?
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 $\...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
3
votes
2answers
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 ...
6
votes
2answers
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 ...
1
vote
1answer
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 ...
6
votes
3answers
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?
1
vote
2answers
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$ ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
3
votes
3answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
103 views

What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free ...

1
3 4
5
6 7
9