# Questions tagged [decision-problem]

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

414 questions
Filter by
Sorted by
Tagged with
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 ...
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$ ...
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 ...
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 ...
56 views

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 ...
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 ...
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 ...
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$, ...
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 ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...
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 ...
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 ...
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 ...
53 views

371 views

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 ...
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 ...
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 ...
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 ...
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?
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 "...
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 ...
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 ...