# Questions tagged [decision-problem]

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

428 questions
Filter by
Sorted by
Tagged with
42 views

### Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
57 views

### Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
19 views

### Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
76 views

### Prove that a 3D packing problem is NP-complete

How can I prove that the following problem is NP-complete? I have a spherical container in which I have to introduce $n$ identical spheres. All of the little spheres have to be inside the container ...
556 views

### What does “Every CFL is decidable” exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
45 views

### How does the length of the output of a problem inform its complexity?

Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. ...
888 views

### Algorithms that run in polynomial time if P=NP

On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
18 views

### Is there a recursive problem encoding the Turing completeness of a model of computation?

Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
64 views

### Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
40 views

### Decision Making using Multiple Variables

What should I learn if I want to make a decision based on multiple variables? Followings are the example of a problem. I have a farm. My variables are weather, humidity of air, humidity of soil, size ...
53 views

### Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
22 views

### Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
52 views

### What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
155 views

### A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
87 views

### NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
301 views

### How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
61 views

### Restriction: polynomial time decision of instance is why needed to “decision Problem”?

I am reading book "combinatorial optimization 3rd edition(Bernhard Korteć Jens Vygen)". (latest version is sixth.) There are some discriptions in this book that I don't understand Not all binary ...
48 views