Questions tagged [decision-problem]

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

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

Deciding whether a context-free grammar's language is empty

Consider the formal problem: Given a context-free grammar $G$, is the language $L(G)$ empty? Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
0
votes
1answer
250 views

Decidability of whether CFL = RL

Let L1 be a language generated by a CFG. Let L2 be a language generated by a regular grammar. Is L1 = L2 ? Is the above problem decidable or undecidable ? If L1 = L2 then L1 $\cap$ L2' = $\phi$ ...
1
vote
1answer
222 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 ...
0
votes
0answers
27 views

Showing a problem is decidable [duplicate]

Hopefully this question is not a duplicate. How do I show the problem below is decidable by describing a Turing machine? Input: Turing machine M Question: Are there infinitely many Turing machines ...
1
vote
1answer
56 views

Post Correspondence problem provable instance

Let the Post Correspondence problem with input $$K = ((x_1, y_1), . . . ,(x_n, y_n)), x_i, y_i ∈ \Sigma^*$$ for $$ i = 1, . . . , n $$ Find a concrete solution for the input $$K = ((001,0), (01, ...
0
votes
0answers
126 views

Is the Language below decidable?

We define a language $L$: $\qquad L=\{\langle M,w,k \rangle \mid M(w) \text{ reaches configuration } \alpha q \beta \text{ with } |\alpha \beta| \geq k \}$ with $M$ Turing machines with state set $Q$...
-1
votes
1answer
599 views

${L^*}$ the Kleene star language is decidable then is $ {L}$ decidable

let ${L^*}$ be the Kleene star language which is definded like that : $${L^*}=\{w_1,w_2, \dots ,w_n\mid n \geq0 \text{ and each $w_i \in L$}\}$$ I have to show of this correct or not ! $$ {L^*}...
3
votes
2answers
318 views

A several equivalent NP definitions

There are two definitions of NP I found: 1) NP is a set of problems that have poly-size certificates, and with a given input, there is a poly-time certifier that checks the proposed solution. 2) NP ...
1
vote
1answer
2k views

Proving that it is undecidable if a Turing machine accepts a language that is its own reverse

I have a Turing machine M. How can I prove that $L(M) = (L(M))^R$ is decidable by constructing a Turing machine that can do this? I know how to figure out if two DFA's accept the same language (using ...
1
vote
1answer
387 views

NP-completeness of triangle removal problem

Triangle removal problem states that, given an undirected graph G, can you pick a subset S of vertices such that removing S will remove all triangles from the old graph and |S| <= k. I was trying ...
1
vote
2answers
467 views

Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable?

This question was made during a class of Computer Theory in Rome, Italy. Let $G$ be a regular grammar, $\Sigma$ its alphabet and $L(G)$ the language generated by $G$ Given a regular grammar $G$, ...
2
votes
1answer
115 views

Solving SAT correctly on all but $poly(m)$ formulas

The question is to show that there is no deterministic polynomial time algorithm that solves SAT correctly on all but $poly(m)$ formulas of size $m$, for every $m \geq 0$ unless $P \ne NP$. I know ...
12
votes
2answers
3k views

Is the equality of two DFAs a decidable problem?

So given two DFAs, is the problem of finding if they generate the same language a Decidable problem? I already know that Equality of two CFL is not Decidable but what about Equality of two DFAs? ...
0
votes
2answers
259 views

Is a Knapsack Problem with only Color Constraints NP-Complete?

I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors. There exists a constraint on ...
3
votes
1answer
922 views

How many possible policies in a Markov Decision Process?

If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \{Hot, Mild, Cold\}$, $A = \{East, West\}$, has 8 possible policies? Isn't it 6 if there are 2 ...
1
vote
1answer
32 views

Finding a graph where the edge set satisfies a set of integer equations

There is an easy and hard version of the problem I am asking about, so I will start with the easy to make for clearer reading. Suppose that we are have a set of vertices $V =\{v_1,v_2,...,v_n\}$ and ...
1
vote
0answers
27 views

Testing whether a set of integers can be written as a combination of module basis elements

Input We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$} Desired Output Return true if there ...
3
votes
3answers
10k views

Prove that Hitting Set is NP-Complete

The Hitting Set Problem (HS) is defined as follow. Let $(C,k$) $C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$ $k \in \mathbb{N}$ We want to know if ...
0
votes
1answer
94 views

Is my problem NP-Hard?

I have a grocery dotted list of pairs which are missing items that I need and I don't have any of them, so I am going to the supermarket. Each pair in the dotted list is the name of the missing item ...
1
vote
1answer
85 views

NP-completeness

Q: Suppose a language A is NP-complete. Is this following statement correct?: A: If there is a polynomial algorithm to solve A, then it can be used to all the problems in NP. My (and some others) ...
1
vote
1answer
4k views

Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete. The ...
1
vote
2answers
195 views

Showing that a language is not recursive

I was given the next function CH(x) that is defined like this: $CH(<M>)$ outputs the computation history of the run of M on epsilon if M halts on epsilon. If it doesn't the function returns ...
1
vote
1answer
101 views

Prove the recursive enumerability of the class of NP-hard context-free languages

I was asked to prove that the next language is recursive enumerable : $$L= \{ \langle G \rangle \mid SAT<L(G) \} $$ where $G$ is a context free grammar and there is a polynomial reduction from ...
7
votes
3answers
909 views

Does every computational problem have a decision version?

Is the following claim correct?: Every computational problem has a decision version of roughly equal computational difficulty. If the above claim is correct, please give a reference for it. (I ...
1
vote
1answer
53 views

Is it always possible to have one part of the reduction?

So I have been asked this question during my comprehensive and I have a few answers to it, I just wanted to check with the community whether I'm on track with them. Is the following statement true? $...
4
votes
1answer
205 views

How do solve assignment of one interval to another?

Is there an efficient algorithm for the following problem? Input: Set of holes and pegs. Each hole/peg is an interval $[\ell,u]$ with integer endpoints. Question: Can all the holes be filled ...
4
votes
1answer
435 views

Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets?

I am trying to wrap my hand around the undecidability proof of the Halting problem, and to me it really seems to be more of a proof about representation than decidability. Namely, the proof that some ...
3
votes
1answer
1k views

Is a circle inside a polygon?

How do I test if a circle (x,y,radius) is inside a polygon ([x,y],[x,y],[x,y],[x,y]...) without touching the edges? Update I decided to do a point in polygon followed by a circle line collision on ...
0
votes
1answer
131 views

construct a TM decides in linear time, if valid bracket

I want to construct a 2-tape Turing Machine, which decides in linear time if the input string over $\Sigma^* := \{(, [, ], )\}$ is a valid bracket. I have not constructed too many TM's yet, this is ...
0
votes
0answers
74 views

determine the language of the independent set problem [duplicate]

Given an undirected graph $G = (V,E)$ an independent set is a subset of nodes $U ⊆ V$, such that no two nodes in U are adjacent. In the independent set problem, $G = (V,E)$ is an undirected graph, $...
1
vote
1answer
371 views

Is the complement of MAX-CLIQUE in NP?

Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$ Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier? If $NP=...
0
votes
1answer
80 views

If M is recognizing L in polynomial time, is it also deciding it in polynomial time?

Assume that a given turing machine $M$ accepts words in the language in $n^k$ or less steps, but words that aren't in the language are rejected in unknown number of steps (the machine might even ...
1
vote
1answer
131 views

Conflict Detection Algorithm

I have been trying to come up with a better algorithm that detects conflicts in the scenarios below. Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we ...
2
votes
2answers
302 views

determining whether a program halts or not

I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine which can decide whether a TM M halts on input w.Now my ...
1
vote
1answer
126 views

Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $

Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer. $$L=\left\{ \...
0
votes
1answer
255 views

Are poly-reductions to PSPACE problems for following problems are known?

List of problems I'm interested in: $\oplus$SAT #SAT-decision Permanent-decision (YES if permanent is greater than given number $k$) I have discovered poly-reduction for MAJSAT (and MAJQBF). However,...
1
vote
2answers
242 views

Decision problems whose verifier is NP

We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$. Is there a name for problems whose verifiers ...
5
votes
2answers
478 views

Is the following Subset Sum variant NP-complete?

Is the following problem NP-hard: Input: $A\subset\mathbb Z, k\in\mathbb N$ Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=0$? For example, on the input $A=\{-...
0
votes
1answer
90 views

Finding suitable NP-complete problem to reduce to my problem

I've been given a set $S$ of natural numbers (non-negative integers) $s_1$, $s_2$,...,$s_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the ...
0
votes
1answer
32 views

Find the maximum (longest) delay to last user in a multicast T. NP complete proof

Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to ...
0
votes
0answers
108 views

The defining property of problems in NP [duplicate]

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
1
vote
1answer
254 views

Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length

The question is as follows: Let's observe the following Post correspondence problem. Input: Two finite lists of words $A$ and $B$ and a natural number $k$. Question: Is there any words correspondence ...
4
votes
1answer
376 views

Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?

Is there any known lower bound on the complexity of subset sum problem? For example, could it be solved in linear time using logarithmic space?
3
votes
2answers
1k views

Having problem understanding the formal definition of NP

So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff; there exists a "...
4
votes
2answers
328 views

Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?

I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard. Is deciding if there's a solution to a single ...
1
vote
0answers
50 views

Program that solves mechanics diagram problems

There is a program, BEATRIX, that can understand textbook physics problems specified by a combination of English text and a diagram. The result of the understanding process is a unified internal model ...
3
votes
1answer
306 views

“Combinational” Decision Graph - Cheapest search algorithm

I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know ...
2
votes
1answer
451 views

4-partition elements summation NP completeness

How can we prove that the following problem $A$ is NP complete? Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
1
vote
0answers
57 views

“Multi-consequent” Decision graph/tree?

As I understand, Decision graph is a directed graph where each vertex is a "Question" (decision to make), and each edge is an "Answer" (decision made for the vertex this edge is coming from). The ...
1
vote
1answer
3k views

Proving that a problem is in NP

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The ...

1 2 3
4
5
9