Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
52 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\vec{{V_i}_j} = \vec{{V_i}_0} + j*\vec{d_i}$. (A natural way ...
-1
votes
0answers
21 views

TM decidable or undecidable problem?

Question: Explain why the following problems are decidable or undecidable (Using rice's theorem where possible). Does the language accepted by a Turing machine contain an even-length word? Holds a ...
22
votes
5answers
2k 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 \...
1
vote
1answer
27 views

Can one show NP-completeness by showing a reduction to 3SAT?

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the ...
3
votes
1answer
216 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
2
votes
1answer
112 views

How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
1
vote
1answer
15 views

How is it possible that for infinite L in R exists subset L' which is not in Re?

Proove that for every infinite $L \in R$ there is a $L' \subseteq L$ s.t $L' \notin RE$. How can I proove it? if sketched on venn diagram it doesn't make sense... From my point of view everything ...
0
votes
1answer
76 views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

The SUBSET SUM decision problem consists of poitive integers a1,...,an; b. We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$ I want to prove that if b is given in unary(...
2
votes
0answers
77 views

NP-hardness proof of an optimization problem with real values and rational input in the decision problem

I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated. For the question, take the ...
0
votes
1answer
34 views

How to prove that the generalized assignment problem (GAP) is NP-hard?

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...
1
vote
0answers
31 views

NP-hardness proof of an optimization problem with real values and real input in the decision problem

Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
-2
votes
2answers
50 views

Is A and C NP-complete?

Given 3 decision problems in $NP$: $A,B,C$. Consider that there are $2$ reduction algorithms, one is $A\le_p B$ (with run-time $n^{10}$) and the other is $B\le_p C$ (with run-time $n^5$). If $B$ is $...
1
vote
1answer
268 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
0
votes
1answer
70 views

Turing-completeness of Goto language with limited constants

This is taken from an old exam of my university that I am using to prepare myself for the coming exam: Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly ...
3
votes
1answer
453 views

A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
2
votes
1answer
36 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
1
vote
1answer
28 views

M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M] $, there would be two ...
7
votes
3answers
7k 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/...
-3
votes
2answers
109 views

Is this solution for the Turing's "halting" problem correct?

I think that Alan Turing's solution for the "halting" problem might be wrong. Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't ...
1
vote
1answer
26 views

Is it NP-hard to check whether for a $k$ there exist both a Cut and a Bisection of value $k$?

Input: An undirected, unweighted graph $G=(V,E)$. A cut is defined as a partition $V=A\dot\cup B$. A bisection is defined as a partition $V=A\dot\cup B$ with $|A|=|B|$ if $|V|$ is even (or $|A|= |B|+1$...
3
votes
1answer
138 views

Show why the following post's correspondence problem is unsolvable

We have the following pairs of strings. $$\begin{bmatrix} aa\\b \end{bmatrix} \begin{bmatrix} ba\\baa \end{bmatrix} \begin{bmatrix} aba\\a \end{bmatrix}$$ The problem is now, to find a concatenation ...
0
votes
0answers
29 views

Traveling salesman problem

Could someone tell me how many stopping points are needed for the traveling salesman to be impractical to be solved by current computing?
1
vote
1answer
27 views

Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters

I am looking for the computational complexity of the following problem. Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
0
votes
0answers
16 views

Check if $L = \{ <M> $ : $M$ simulated on $<M>$ halts after max. $32$ steps $\}$ is decidable

The confusing part is, that $M$ basically is simulated on its own encoding $\langle M\rangle$. Nevertheless, I would claim its decidable by simply creating the following $TM$ $T$: check if $\langle M\...
1
vote
0answers
32 views

Computing a threshold function

Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as \begin{equation} g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x). \end{equation} Let us be ...
16
votes
2answers
2k 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 ...
1
vote
1answer
34 views

Is this string substitution problem decidable?

We have the following task: Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be ...
1
vote
1answer
36 views

Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
1
vote
0answers
13 views

$W$-hierarchy and parameterized search problems

I have two related questions: What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
0
votes
1answer
90 views

A question on decidability

I have a homework question that is as follows: L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P ...
1
vote
2answers
75 views

Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A. Are there ...
-2
votes
1answer
54 views

Reduction from 3SAT to SUBSET-SUM

The reduction from 3SAT to SUBSET-SUM includes building a table as follows: Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct ...
1
vote
1answer
68 views

Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?

The negative answer to decidable = non-contracting grammar? suggests the following question: Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. ...
0
votes
0answers
24 views

Purpose of Acceptance Problem

I am confused about the purpose/statement of the Acceptance problem: $A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$ It can be shown that $A_{TM}$ is uncomputable, so we know that, ...
1
vote
2answers
49 views

Proving a problem is NP Hard

Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted ...
0
votes
0answers
17 views

Predictive score ? how?

let say I have a sequence of values ... The values X and Y can be either number or data structures or states ... and so on ... Example: Value X can be followed by any of "n" other values Y1,...
0
votes
1answer
19 views

Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

Here’s the decision problem: Suppose I have N positive integers encoded in base-2 (as oppose to unary) Are these integers precisely the integers 1-N in some order? This is related to the Hamiltonian ...
0
votes
1answer
39 views

Sorting n weight disks with decision tree

I was refreshing some old tests about sorting algorithms, there was a question as follow: Question: we have n weight disks with different weights and we want to ...
-2
votes
2answers
111 views

Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ...
0
votes
1answer
157 views

Show that this language is decidable?

Let A = { | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable. The questions seems simple so I designed the following TM D that decides whether ...
1
vote
3answers
144 views

Is polynomial over x with real roots decidable?

Today while I'm looking at definition of Algorithm from Sipser's textbook, he defined the following language: $$D_1 = \{ p \mid\ p\text{ is polynomial over }x\text{ with integral roots}\}$$. This ...
0
votes
1answer
20 views

Are there search problems that cannot be written as decision problems?

I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem. Of course, if you have a finite ...
1
vote
1answer
38 views

How does reduction of a decision problem work?

I am given the following problem description: Given $l$ lists, $L_1$, $L_2$, . . .$L_l$ each containing $N$ bit vectors of $n$ bits each, we want to find tuples $(x_1,···,x_l)$ with $x_i$ in the ...
1
vote
1answer
21 views

Predicate variant of Assignment Problem

Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that \begin{align} \forall p \in P \; p(f(p)) \end{...
2
votes
2answers
83 views

One tape nondeterministic Turing machine accepting non-palindromes

I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time. My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a ...
0
votes
1answer
434 views

Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
1
vote
1answer
88 views

show that NP is a subset of decidable languages

More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D" My problem is that I always assumed that NP is decidable, but to prove it, I never ...
1
vote
1answer
34 views

Is this "superset existence" problem NP-complete?

The "Superset Existence Problem": Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets? To me, ...
1
vote
1answer
72 views

Understanding P vs NP

I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
0
votes
0answers
32 views

Difference longest path problem and underlying decision problem [duplicate]

I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-...

1
2 3 4 5
10