Questions tagged [decision-problem]

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

61 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...