Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
4
votes
2answers
2k views

Is global non-convex optimization NP-complete?

Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
0
votes
1answer
307 views

If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP

If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP. I am struggling with figuring this out. I know this means Y can be reduced to X, so if I ...
0
votes
1answer
194 views

How to reduce language is finite to language is regular?

I'm trying to reduce $FIN \leq REGU$, where: $$FIN = \{ \langle M \rangle \vert T(M) < \infty \} \\ REGU = \{\langle M \rangle \vert T(M) \in REG\}$$ Now one thing I have done so far is this: $...
1
vote
1answer
777 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 ...
2
votes
2answers
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 ...
0
votes
1answer
1k views

Is L={0,1}* without strings that start with 00 decidable?

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.
1
vote
1answer
79 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 ...
0
votes
1answer
187 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 ...
2
votes
1answer
249 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$ ...
23
votes
2answers
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. ...
0
votes
1answer
57 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^*$...
0
votes
2answers
464 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 ...
1
vote
1answer
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 ...
3
votes
0answers
88 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 ...
-3
votes
1answer
112 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 ...
3
votes
2answers
643 views

Do all algorithms aim to solve decision problems?

An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more ...
0
votes
0answers
443 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
265 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
249 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
62 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
674 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^*}...
4
votes
2answers
360 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
423 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
689 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
4k 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
274 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
1k 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
33 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
12k 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
98 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
86 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
199 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
110 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
1k 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
55 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
207 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
493 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
133 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
403 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
85 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
135 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
362 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 2 3
4
5
9