Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
-1
votes
0answers
20 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 ...
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
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 ...
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 ...
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
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 ...
-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 $...
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 ...
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 ...
-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$...
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?
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
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
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 ...
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 ...
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
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
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(...
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
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
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 ...
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 ...
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-...
0
votes
1answer
61 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
37 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
20 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
43 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?
0
votes
1answer
48 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
107 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
41 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
2 3 4 5
10