# Questions tagged [decision-problem]

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

428 questions
Filter by
Sorted by
Tagged with
18 views

### 1-Tape Non-deterministic Turing machine and non-palindromes

I have to design a Non-deterministic 1-Tape Turing machine that accepts only non-palindromes in O (n log n). But my best shot was only in O(n^2). How can I use the properties of NTM on a single tape ...
145 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?
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 ...
20 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, ...
52 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 ...
32 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 ...
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-...
2k views

248 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 ...
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 ...
19 views

2k views

71 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 ...
64 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$:...
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 ...
37 views

38 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 ...