# Questions tagged [decision-problem]

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

414 questions
Filter by
Sorted by
Tagged with
25 views

### Is the set $\{<M> | L(M) \text{is a finite set}\}$ RE, co-RE or neither? [duplicate]

$<M>$ is the encoding of a TM and L(M) is the language accepted.
67 views

### What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
29 views

### Decision problems involving finite automata

A finite automaton (FA), A, may accept or reject its own encoding, {A}. A machine, M, can be written that accepts {A} iff A rejects {A}. Turing gave a famous proof that M is not an FA. The proof ...
897 views

### Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
166 views

### Does this Haskell code represent a decision procedure for a theorem?

The following is a natural language description of a first order theory from Worboys. Only Axiom 11 and the Theorem 4 are written in mathematical notation. Theory 1 Aland, Bland, Cland, and Dland are ...
15k views

### Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
257 views

### reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...
118 views

### Time complexity of a language whose alphabet has a single symbol

Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$. Can anything be said about the ...
309 views

### What is the algorithm for a decider to get the language accepted by a DFA?

I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
631 views

### Is this a correct way to show that a problem is coNP-complete?

Let $A$ be a problem that I want to show it is coNP-complete. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show ...
48 views

### How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there ...
453 views

### Why SAT Requires A Non-determinstic Algorithm?

I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness). I do understand the difference between a ...
35 views

### Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
105 views

### Defining a graph decision problem not in NP

I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the ...
533 views

### Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
42 views

54 views

### How to prove existence of the language

Consider such question: (Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$. I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
75 views

### How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it? Perhaps: SZ shows natural polynomials are equal iff it shows those ...
883 views

### Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
185 views

### Can all types of problems be converted to decision problems?

We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is ...
259 views

### A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...
342 views

### Is it NP complete to decide whether a graph has $k$ disjoint triangles?

I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$ but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in ...
618 views

### Are there any optimization problems in P whose decision version is hard?

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
240 views

### Modified Subset Sum Problem

Given an array of $n$ integers $A$, and some value $m$, determine if it is possible, by using certain amounts of each element, to get a total sum equal to $m$. Consider that you can use any amount of ...
117 views

645 views

### How does this reduction to prove undecidability account for epsilon?

I have the following proof that the Empty String problem: ES = {M | M accepts $\epsilon$} is undecidable: $f<M,w>$ = Construct a new machine $M_2$ such that: $M_2$ = given input x erase x ...
153 views

### Decision problem for a Regular Langauge

I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof. For example: Given ...
1k views

Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable? I'm drawing a blank on this one.
71 views

### How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

Every function problem has a corresponding decision problem, which is simply the graph of the function problem, according to https://en.wikipedia.org/wiki/Decision_problem#Function_problems which ...
172 views

### Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?

In this question Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have ...
244 views

### Solving diophantine equations — does having a bound on the size of the solution help?

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$: H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ ...
3k views

### How is the traveling salesman problem verifiable in polynomial time?

So I understand the idea that the decision problem is defined as Is there a path P such that the cost is lower than C? and you can easily check this is true by verifying a path you receive. ...
54 views

### What is the complexity of the following problem?

Input: $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^*$...
420 views

### Definition of NP [duplicate]

We know that NP is the class of languages recognized by a nondeterministic Turing machine (NTM) in polynomial time. I've also read that NP is the class of problems can be solved by NTM in polynomial ...
44 views

### Checking if the mimimum is unique

We have a finite poset and its subset $S$. We can enumerate elements of $S$ using an iterator. I need to check if there are more than one minimal elements of $S$ (regarding the above poset). The ...
82 views

### Is there a generic procedure to produce (hard enough) decision problems?

This comment by @DerekElkins suggests a general method of constructing decision problems for problems with bit-strings as output, of which a slightly formalised version is the following: Given a ...
110 views

### How are optimal weights computed in best-Worst Multi-criteria Decision Making Method (Step 5 of BWM)? Can someone explain it with an example?

Title: Best-worst multi-criteria decision-making method Author:Jafar Rezaei, Pub: Omega 53 (2015) 49-57 BWMCD From this example How are optimal weights (W1*, W2* etc) computed on Page:22 ? what are ...