Questions tagged [decision-problem]
A question in some formal system with a yes-or-no answer.
61
questions with no upvoted or accepted answers
21
votes
4answers
1k views
Algorithm to test whether a language is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
18
votes
0answers
382 views
Is finding a weight-balanced tree NP-hard?
In the following, we consider binary trees where only the leaves have weights.
Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves.
Let $T.l$ and $T.r$ be the left child and ...
13
votes
0answers
593 views
Test whether two languages are equal, when give in algebraic form
This sub-problem is motivated by Algorithm to test whether a language is regular.
Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
5
votes
0answers
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 ...
4
votes
0answers
92 views
Turing reductions by NX ∩ coNX and binary relation problems
Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
4
votes
0answers
86 views
Proof that $P$ is robust against switching between polynomially equivalent encodings
Lemma 34.1
Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and only ...
3
votes
1answer
267 views
A variation of the halting problem
Given an infinite set $S \subseteq \mathbb{N}$, define the language:
$L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$
where $T_M$ is the ...
3
votes
0answers
107 views
A special case of the SUBSET SUM problem
Consider the following special case of SUBSET SUM
Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary.
Encoding: These inputs (...
3
votes
1answer
150 views
Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable
Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$.
This problem ...
3
votes
0answers
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 ...
3
votes
0answers
156 views
I need a better data structure than a graph with condition nodes
Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of ...
3
votes
0answers
214 views
Is this modification of the subset-sum problem NP-complete?
Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, ...
3
votes
0answers
77 views
Online algorithm for planning
Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A ...
2
votes
0answers
47 views
An optimization version of 2QBF: is it $\mathsf{NP}^{\mathsf{NP}}$-hard?
I am studying the computational complexity of the following decision problem related to 2QBF:
Input: a 3-CNF formula $\varphi$ over $X \cup Y$, where $X$, $Y$ are disjoint sets of propositional ...
2
votes
1answer
68 views
How To Show That B is Semi-Decidable Given A
I am preparing for my Computational Theory final and ran into this exact problem :
B={ x | there exists a prefix of x that is in A}.
Show that B is semi-decidable. In other words, you need to ...
2
votes
0answers
38 views
Decision problems with complex input validation
In an answer to a question regarding input validation in decision problems, @Apass Jack wrote
It is easy to check whether a problem instance is a valid instance or not for almost all decision ...
2
votes
0answers
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 ...
2
votes
0answers
166 views
Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)
Given the following NP-complete problem:
PARTITION
Input: A list of positive integers $a_1, a_2, \dots, a_n$.
Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
2
votes
0answers
346 views
Determining whether a number is a perfect square without computing its square root
One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without ...
2
votes
0answers
256 views
Proving NP-Completeness by reduction
I'm given a more restricted version of 3-SAT called 3-SAT-M:
Problem: 3-SAT-M
INPUT: A set of clauses C {c1,...,ck} over n boolean
variables {x1,...,xn}, where every clause contains exactly three
...
2
votes
0answers
320 views
What are some results for non-trivial lower bounds for the time complexity of decision problems?
Typically decision problems are studied in complexity theory and function problems are studied in the Analysis of Algorithms. Unfortunately, Complexity Theory tends to abstract over the exact time ...
2
votes
0answers
217 views
Travelling salesman problem with detours
I am interested if there exists a following version of the travelling salesman problem:
INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
1
vote
0answers
72 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 ...
1
vote
0answers
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. ...
1
vote
0answers
30 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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
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 ...
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 ...
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 ...
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
0answers
161 views
Rice theorem to prove Emptiness problem
Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable?
With the emptiness problem I mean the question if a certain machine doens't accept any input ?
If you ...
1
vote
0answers
305 views
Reducing a problem with two knapsack that needs equal number of items from Knapsack?
I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness.
The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
1
vote
0answers
226 views
Decision problem 3SAT and Bip[3-1]
Consider the decision problem Bip[3–1], define as follows:
Instance: $G = (S,T;E)$, bipartite graph, with $d_G(s) = 3$ for all $s \in S$.
Question: Does there exist $S' ⊆ S$ such that in $H = [S'∪T]...
1
vote
0answers
68 views
turing machine decidability language
I must show that this language is decidable but I think it's not
{D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ }
Here what I think
I give a reduction from E(TM). I suppose that this ...
1
vote
0answers
611 views
Showing that $H'$ is not semi-decidable
I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
1
vote
0answers
75 views
Efficiently decidable logics
So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then ...
1
vote
0answers
66 views
Relevant subtree and relevant leaf in Machine Learning Decision Trees
I'm currently studying Decision Trees and the definition of a decision tree in our course is somewhat obscure for me. Nowhere in other online definitions of decision trees do I find something about ...
1
vote
0answers
350 views
Does FNP-complete = NP-complete?
I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong.
So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
1
vote
1answer
84 views
Deciding whether a CFG is parity absent
Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ ...
0
votes
0answers
11 views
Let $L \in \mathrm{\mathbf{NP}}$, is there a polynomial-time oracle Turing machine $B$ that $B^{L}$ on input $x \in L$ outputs a certificate for $x$?
Let $L \in \mathrm{\mathbf{NP}}$ and a verifier Turing machine $M$ for $L$.
Is there a polynomial-time oracle Turing machine $B$ that $B^{L}$ on input $x \in L$ outputs a certificate for $x$ (with ...
0
votes
1answer
78 views
Enumerator for Word and Halting Problem
in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1answer
43 views
Turing-completeness of Goto language with limited constants
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly ...
0
votes
0answers
19 views
What decision problems are their that are outside of elementary but still decidable
What decision problems are their that are outside of ELEMENTARY but still decidable?
I'm curious about problems that are still solveable, but take a very long time to do so.
0
votes
0answers
49 views
Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?
Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$?
$s$ = $1,2,3,4,5,6$
$c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[...
0
votes
0answers
40 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$.
...
0
votes
0answers
14 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 ...
0
votes
0answers
18 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 ...
0
votes
0answers
48 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?
0
votes
0answers
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 ...
