Questions tagged [decision-problem]

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

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

Can we DISPROVE that a problem is NP-complete

So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
1
vote
1answer
20 views

Can I reduce from the recognition version of one probem to another without knowing the exact parameter?

I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
1
vote
1answer
46 views

How do I prove that the clique problem is polynomial-time reducible to the odd cycle transversal problem?

I have the following problem: Let $H=(W, F)$ a graph and $k \in \mathbb{N^*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We ...
1
vote
1answer
45 views

Is proving NP-(in)completeness generally NP-complete?

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
0
votes
0answers
22 views

Is this variant of Subset Product NP-hard? [duplicate]

Given a set $Y$ with whole number positive divisors of $N$, is there a combination of divisors that have a product equal to $N$? Does Subset Product remain NP-hard when whole number divisors are only ...
0
votes
0answers
20 views

Strategy to reduce between decision problems

I'm very new to complexity theory, please help me fill in the gaps in whatever knowledge I have acquired till now. A decision problem is a problem $X(D)$ that outputs for each input instance $I$, a ...
0
votes
1answer
33 views

Independent set problem with given black box

I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why. Suppose that I'm given a polynomial ...
3
votes
1answer
51 views

Deciding whether a set of relations can be composed to the empty relation

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
2
votes
2answers
47 views

Problem reduction: Can YES-Instances also be mapped to NO-Instances if there is perfect correspondence?

Definition: Problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, ...
0
votes
1answer
36 views

NP-Completeness of SAT with given hamming weight k [duplicate]

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction. Input: A propositional formula $\varphi$ and a number $k$. Output: Yes if exists an valuation $\...
0
votes
1answer
35 views

Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?

I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-...
2
votes
1answer
69 views

Find the class of the problem PP1 and PP2 using the information given below

Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
3
votes
1answer
73 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 $\cdots,\vec{{V_i}_{-1}},\vec{{V_i}_0},\vec{{V_i}_1},\cdots$ ...
1
vote
1answer
35 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
18 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
33 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
88 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
52 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
35 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
1answer
37 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
31 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
118 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
28 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
31 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
143 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
29 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
33 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
39 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
15 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
76 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
86 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
113 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
116 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
70 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
101 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
20 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
18 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
42 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
127 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
376 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
198 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
30 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
40 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
98 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
541 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
116 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
35 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
2 3 4 5
10