Questions tagged [decision-problem]

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

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
3answers
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
349 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 ...
12
votes
0answers
529 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
141 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
81 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
85 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
0answers
89 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
115 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
68 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
155 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
211 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
74 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
1answer
43 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
36 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
197 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
139 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
328 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
206 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 ...
2
votes
0answers
303 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
206 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 ...
1
vote
0answers
27 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
160 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 ...
1
vote
1answer
208 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
49 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
51 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
152 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
255 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
64 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
515 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
61 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
65 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
323 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
75 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
58 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 ...
0
votes
0answers
57 views

What Makes A TM undecidable (using Recursion Theorem)

PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B. B =“On input w: Obtain, via the recursion theorem, ...
0
votes
0answers
13 views

Decision Tables Column Colouring

I am learning about decision tables and am confused by the colouring in the text book's mark scheme for a question I'm working on. I can not see why some of the columns have been coloured grey. Rather ...
0
votes
0answers
58 views

Is summing a function over all subsets in PP?

Consider the following decision problem: Input: a set $X = \{x_1, \ldots, x_n\}$, a mapping $f \colon 2^X \mapsto \mathbb{N}$ such that for $f(Y)$ is computed in polynomial time for any $Y \subseteq ...
0
votes
0answers
14 views

Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?

The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem. Imagine a row of commands: ...
0
votes
0answers
18 views

Does $FL = FP$ if and only if $L = P$?

I believe the answer is yes. However, I fear I might be overlooking something. In general, what can one say about the equivalence of two complexity classes for decisions problems and the equivalence ...
0
votes
0answers
44 views

Given a solution for the post correspondence problem, is it co-semidecidable if the solution is a palindrom?

This was an old exam question. I think, though, that it is some sort of trick question. Isn't this simply decidable and therefore also trivially co-semidecidable? Because I wouldn't know how to ...
0
votes
0answers
260 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
0answers
123 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$...
0
votes
0answers
159 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
0
votes
1answer
714 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
votes
1answer
580 views

How do you know a problems is non-computable?

I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which ...
-1
votes
1answer
275 views

Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem: $$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$ to a problem, where i have a matrix ...
-3
votes
1answer
106 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 ...