Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
15 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
33 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
16 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
28 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
157 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
63 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
21 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
58 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 ...
1
vote
1answer
33 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
29 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-...
0
votes
1answer
57 views

Another version of the 3-coloring decision problem?

Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color? Is there a ...
1
vote
1answer
35 views

PCP when upper and lower words have different length

The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,...
0
votes
0answers
19 views

What's the union between a decision problem and its complement

I see the union of problems as something like this: $P=F\cup G$ $P(\omega):$ $\;\;\;\;if\; F(\omega)==True: return \;\; True$ $\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$ $\;\;\;\;else: ...
0
votes
0answers
36 views

Are there any tetrational-time problems?

I know there exists problems decidable in polynomial-time, exponential-time, etc. I couldn't find any tetrational-time problems, however. Are there any and if not, why?
1
vote
1answer
42 views

Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property: For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct ...
1
vote
1answer
23 views

Different Classes of NP [closed]

I was solving problems related to P and NP where I encountered the following problem: Given a standard definition of NP, if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = ...
0
votes
0answers
67 views

3-Sat reduction to facility location problem

I'm learning about NP problems and I this problem which is a bit challenging for me. You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
2
votes
0answers
31 views

Proving that DCONN is NL-Complete

I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed. Problem definitions: RCH: Given a ...
1
vote
2answers
204 views

NP-completeness of testing whether a SAT formula does not contain any redundant clause

This paper explains that testing the irredundancy of a SAT instance is NP-complete. But I don't understand the theorem/reduction. How would one reduce 3SAT or k-SAT to this problem, for example?
0
votes
1answer
48 views

If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
1
vote
1answer
107 views

How to convert a decision tree to an automaton?

From what I know, a problem can be transformed to a yes/no answer, which can be described by a decision tree. Solution to a problem also can be represented by a set of strings (a language), which ...
0
votes
1answer
15 views

What does a kernel of size n,n^2 ,… mean?

So according to Wikipedia, In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the ...
-1
votes
3answers
193 views

Why don't passwords prove P != NP?

Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ...
1
vote
1answer
54 views

Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$. My idea: It is co-semi-decidable since as soon as i ...
0
votes
1answer
57 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
1
vote
1answer
51 views

Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable. First of all: I don't understand, ...
1
vote
1answer
95 views

Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1answer
45 views

Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

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}^c \subseteq \text{Goto}$. This language contains exactly ...
-1
votes
2answers
61 views

Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every language contain the $\...
0
votes
1answer
58 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
95 views

I have a decision problem with $2^n$ bit sized certificates, how would I verify my decision problem efficiently if it is in $NP$?

Decision Problem: Is $2^k$ + $M$ a prime? The inputs for both $K$ and $M$ are integers only. The solution is the sum of $2^k$+$M$. (Use AKS to decide prime) The powers of 2 have approximately $2^n$ ...
1
vote
1answer
74 views

Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
0
votes
1answer
72 views

Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:...
0
votes
2answers
17 views

Proof of Co-Problem being in NP if Problem is in NP using negated output

Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof? Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
1
vote
2answers
37 views

Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

I'm trying to figure out whether infinite language change the answer. Show that the following language is decidable: $$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)...
0
votes
1answer
22 views

Pick elements that don't exhaust any set

The following is an NP-Complete problem: Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers. ...
0
votes
1answer
40 views

Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable. I would say ...
1
vote
1answer
36 views

why is $\Pi_2$ smaller than $NP\cap coNP$

Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT} \}$. What is the smallest class that $A$ is known to belong to? Apparently, the answer is $\Pi_2$, although I ...
3
votes
1answer
297 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
43 views

Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
0
votes
1answer
40 views

checking whether turing machine passes at least k>2 states before accepting a word

$L=\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that $M$ passes at least $k>2$ distinct states before accepting $w$}\}$ I try to think of reduction to prove that this language is ...
0
votes
1answer
54 views

Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes? $SUM$ = 10 $S$ = $[4,6]$ $No$, Sum of Two Primes $5 + 5 = 10$. ...
2
votes
1answer
81 views

Complexity of Integer Factorization

In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142): A language $L$ is in NP if there is a turing machine $M$ with the ...
2
votes
0answers
48 views

An optimization version of 2QBF: is it $\mathsf{NP}^{\mathsf{NP}}$-hard?

I am studying the computational complexity of the following decision problem related to 2QBF: Input: a 3-CNF formula $\varphi$ over $X \cup Y$, where $X$, $Y$ are disjoint sets of propositional ...
1
vote
1answer
40 views

Why Right-Division of regular language with RE\E language is regualr?

I think I can't understand the meaning of language being decidable. The next case makes no sense to me: Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
0
votes
1answer
34 views

Is necessarily the following language not decideable

For A,B that are not decidable, does AB U BA not necessarily decidable? I think that the answer is NO. Not necessarily. I thought about the following example, but it does not refute exactly: If we ...
0
votes
0answers
19 views

What decision problems are their that are outside of elementary but still decidable

What decision problems are their that are outside of ELEMENTARY but still decidable? I'm curious about problems that are still solveable, but take a very long time to do so.
0
votes
0answers
49 views

Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?

Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$? $s$ = $1,2,3,4,5,6$ $c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[...
2
votes
1answer
135 views

Combining 2 problems in NP into one

Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$. Can S be solved with oracle access to only one problem in $NP$? ...
0
votes
1answer
26 views

Is there a polynomial time algorithm for this decision problem?

Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$? False Result Example $N$ = 8 $M$ = 16 1, 2, 4, 8, 16 There is no integer that is NOT a factor of $N$ that ...

1
2 3 4 5
9