Questions tagged [decision-problem]
A question in some formal system with a yes-or-no answer.
64
questions with no upvoted or accepted answers
21
votes
4answers
2k 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
400 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
608 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
215 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
87 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 ...
4
votes
0answers
158 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
1answer
294 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
111 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
153 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
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
0answers
218 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
31 views
Proving that DCONN is NL-Complete
I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed.
Problem definitions:
RCH: Given 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
83 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
39 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
255 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
173 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
352 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
284 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
327 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
219 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
1answer
32 views
Cyclic tour minimizing total weight
I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.
I saw the question below on an old stack exchange question when looking to ...
1
vote
0answers
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 ...
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
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 ...
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
248 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
58 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
166 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
329 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
293 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
70 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
631 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
81 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
361 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
86 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
19 views
What's the union between a decision problem and its complement
I see the union of problems as something like this:
$P=F\cup G$
$P(\omega):$
$\;\;\;\;if\; F(\omega)==True: return \;\; True$
$\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$
$\;\;\;\;else: ...
0
votes
0answers
36 views
Are there any tetrational-time problems?
I know there exists problems decidable in polynomial-time, exponential-time, etc. I couldn't find any tetrational-time problems, however. Are there any and if not, why?
0
votes
0answers
65 views
3-Sat reduction to facility location problem
I'm learning about NP problems and I this problem which is a bit challenging for me.
You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
0
votes
1answer
58 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
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$.
...
0
votes
0answers
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 ...
