Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
34 views

Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily?

Let's determine if an expression is tautological or not and let's try this expression: ((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c). We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
user avatar
3 votes
1 answer
81 views

Decide whether regular language contains a word $w$ for which $|w| = n^2$

Task: Input: DFA $M = (Z, Σ, δ, q_S, E)$ $T(M)$ := Language that $M$ accepts. Question: Does $T(M)$ contain at least one word $w$ such that $|w| = n^2$ with $n \in \mathbb{N}$$ ?$ My attempt: Since ...
user avatar
2 votes
1 answer
121 views

Complexity of the (Complete/Assign) 3-SAT problem?

A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies. Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...
user avatar
9 votes
1 answer
2k views

Why rectangle packing is NP-hard but maybe not in NP?

Recently I studied a MIT open course. In lecture2, it is stated that Rectangle Packing is NP-hard. I can understand this because the problem can be reduced to 3-partition problem But I don't know why ...
user avatar
  • 153
0 votes
1 answer
39 views

Reducing to an NP-complete problem

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$? I think we should be able to say that $R$ is in NP since an instance of $...
user avatar
0 votes
1 answer
27 views

Knapsack with quadratic constraint

Suppose I have a variant of the knapsack problem: $$\max_{x} \sum_{i=1}^n v_ix_i$$ $$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$ for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
user avatar
2 votes
1 answer
57 views

NP-completeness of some problems on assigning candidates to departments

Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
user avatar
  • 21
-1 votes
1 answer
34 views

What kind of problems in the world can be classified into PSPACE categories?

For instance can we categorize the following problems into NP-Hard ? Is the Universe finite ? Is there life after death ? What came first, the chicken or the egg ? My question is more around what ...
user avatar
1 vote
2 answers
471 views

Prove that a quadratically-constrained linear program (QCLP) is NP-Complete

Show that if we strengthen linear programming by also allowing constraints of the form $$ \sum_{i,j = 1}^n a_{ij} x_i x_j = b, $$ for integers $b$ and $a_{ij}$, then the problem becomes NP-complete. ...
user avatar
  • 113
0 votes
0 answers
44 views

Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness

The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$. Minimum Vertex Bisection problem gives you a bisection of the smallest size. ...
user avatar
0 votes
0 answers
22 views

Does deciding the following language take polynomial time or constant time?

I've written an algorithm that decides the following language: $$ \{ \langle G, H \rangle \mid G, H \text{ are undirected graphs, } \lvert V_H \rvert \leq 10 \text{ and } G \text { is isomorphic to a ...
user avatar
2 votes
3 answers
457 views

Deciding whether an integer polynomial has an integer root

This is a question written by my instructor Z. Loria . Consider the following problem: Given a polynomial $p(x) = \sum_{i=0}^n a_ix^i$, where $a_i$ are integers, is there a natural number $n \in \...
user avatar
  • 117
1 vote
1 answer
19 views

Condition for detection of collision in an algorithmic problem

While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say Let’s deepen the ...
user avatar
6 votes
0 answers
82 views

Complexity of frog game on graphs is exponential, or can we do better?

Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
user avatar
  • 175
0 votes
0 answers
66 views

Can this kind of NP-Hard problem be approximated?

Consider this kind of optimization problem: (1) The problem aims to minimize a value. Let n denote this value. (2) To determine whether n = 0 is a NP-Complete problem. It is obvious that this kind of ...
user avatar
  • 69
-2 votes
1 answer
34 views

Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?
user avatar
  • 1
2 votes
2 answers
902 views

What is a witness string? I unable to understand the concept

From the text A language $L$ is in the class $NP$ iff there exists a polynomial-time Turing machine, denoted $V$, that gets an input string $x$ as well as a read-only string called the witness $w$, ...
user avatar
  • 123
1 vote
1 answer
470 views

Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete

I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete. Sparse Subgraph problem: Input: Undirected graph $G(V,E)$, two ...
user avatar
  • 133
0 votes
0 answers
46 views

Show that a problem about permutations is NP-Complete

I want to prove that the following problem is NP-Complete. Input: Set $S = \{s_1, \dots, s_n \}$, set $T \subset S \times S$, that contains ordered pairs $(s_i, s_j) : s_i \neq s_j$, and an integer $...
user avatar
  • 133
0 votes
2 answers
91 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 ...
user avatar
  • 1
1 vote
1 answer
23 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(...
user avatar
1 vote
1 answer
55 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 ...
user avatar
  • 75
1 vote
1 answer
50 views

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

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
user avatar
  • 161
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
22 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 ...
user avatar
0 votes
1 answer
61 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 ...
user avatar
3 votes
1 answer
55 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 ...
user avatar
2 votes
2 answers
79 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, ...
user avatar
0 votes
1 answer
40 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 $\...
user avatar
  • 103
0 votes
1 answer
36 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-...
user avatar
  • 23
2 votes
1 answer
86 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 ...
user avatar
  • 23
3 votes
1 answer
77 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$ ...
user avatar
1 vote
1 answer
47 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 ...
user avatar
1 vote
1 answer
73 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 ...
user avatar
1 vote
0 answers
35 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 ...
user avatar
2 votes
0 answers
94 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 ...
user avatar
-2 votes
2 answers
53 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 $...
user avatar
0 votes
1 answer
59 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 ...
user avatar
1 vote
1 answer
46 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\...
user avatar
1 vote
1 answer
36 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 ...
user avatar
  • 25
-3 votes
2 answers
139 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 ...
user avatar
1 vote
1 answer
34 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$...
user avatar
  • 639
0 votes
0 answers
32 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?
user avatar
  • 131
3 votes
1 answer
145 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 ...
user avatar
  • 59
0 votes
0 answers
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\...
user avatar
  • 59
1 vote
1 answer
32 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 ...
user avatar
  • 21
1 vote
0 answers
35 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 ...
user avatar
1 vote
1 answer
44 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 ...
user avatar
1 vote
0 answers
19 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? ...
user avatar
0 votes
1 answer
100 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 ...
user avatar

1
2 3 4 5
10