Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [decision-problem]

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

2
votes
0answers
32 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 ...
0
votes
0answers
12 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 ...
1
vote
2answers
40 views

Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset? I'm ...
3
votes
0answers
73 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 (...
0
votes
1answer
19 views

Fine-grained complexity of 3-CNF formula evaluation

It's well known that 3-SAT is in NP, which means that one can evaluate a 3-CNF formula in polynomial time. However, I was wondering what the tightest upper bound is for formula verification, expressed ...
3
votes
2answers
184 views

Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an ...
2
votes
1answer
43 views

Reducing 3SAT to a Set Splitting Problem

I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the ...
1
vote
1answer
13 views

Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$

I've been struggling for a while trying to solve this problem: Show that the following problem is in $\mathbf{NP}$: Check that a system of linear equations with $m$ integer variables and integer ...
4
votes
1answer
274 views

What's after EXPSPACE?

As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE. Thinking about this question, I came up with a ...
3
votes
2answers
91 views

Interesting logic problems

I've just began a course on logic and learned the following : De Morgan's laws Normal forms How to represent a logical formula (using or, and, not operators) using binary trees How to ...
3
votes
1answer
28 views

Why is EXACT-CLIQUE not in co-NP?

In my lecture I saw the problem of $\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$ I understand this problem is obviously not in NP as we would need ...
0
votes
0answers
56 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 ...
2
votes
1answer
44 views

What is wrong with this reduction from vertex cover to binary programming?

I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming. Here are the problem statements. Vertex Cover Decision Problem Instance: A ...
0
votes
0answers
10 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
36 views

Why finding out an independent set of size k is in NP-C and not in P? [duplicate]

I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P. P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is ...
0
votes
0answers
17 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 ...
1
vote
1answer
40 views

Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
3
votes
1answer
429 views

So if a problem is more difficult the language it represents is smaller?

I'm reading the definition of polynomial time reducible: Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in ...
1
vote
2answers
97 views

Why are not all recursive languages undecidable?

I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If ...
0
votes
0answers
12 views

How to know if a lanugae is undecidable or semi-decidable

I recently learnt about undecidable languages and semi-decidable languages. But I am still quite confused on how I can determine if a language is semi-decidable. Is there any standard theorem or axiom ...
3
votes
1answer
62 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 ...
0
votes
0answers
19 views

Is the set $\{<M> | L(M) \text{is a finite set}\}$ RE, co-RE or neither? [duplicate]

$<M>$ is the encoding of a TM and L(M) is the language accepted.
0
votes
2answers
43 views

What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
1
vote
0answers
22 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 ...
0
votes
0answers
26 views

Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
1
vote
2answers
137 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
0
votes
0answers
22 views

How to prove that a language is sparse?

I have a decision problem. I feel like the problem has very limited expressive power so that it can not be NP-complete. What are the reasonable ways to try to prove the rough statement "it has limited ...
1
vote
0answers
148 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 ...
64
votes
7answers
15k views

Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
1
vote
1answer
33 views

reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...
2
votes
1answer
111 views

Time complexity of a language whose alphabet has a single symbol

Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$. Can anything be said about the ...
2
votes
1answer
64 views

What is the algorithm for a decider to get the language accepted by a DFA?

I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
1
vote
1answer
148 views

Is this a correct way to show that a problem is coNP-complete?

Let $A$ be a problem that I want to show it is coNP-complete. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show ...
2
votes
1answer
39 views

How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there ...
2
votes
2answers
231 views

Why SAT Requires A Non-determinstic Algorithm?

I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness). I do understand the difference between a ...
1
vote
1answer
29 views

Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
1
vote
3answers
81 views

Defining a graph decision problem not in NP

I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the ...
1
vote
2answers
166 views

Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
0
votes
1answer
33 views

Cook completeness of a variant of Vertex Cover

Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$? Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$ Output: YES if there exists a vertex cover $C'\...
0
votes
1answer
33 views

Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

$\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly ...
5
votes
1answer
56 views

Applying a permutation on a sequence with multiplication

We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if ...
0
votes
0answers
17 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 ...
2
votes
1answer
41 views

No common terms between polynomials: an efficient check?

The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$. A brute force solution would be to ...
8
votes
1answer
100 views

Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following: $L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$ $L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$ Claim $L_1 \leq_P ...
3
votes
0answers
39 views

How to prove existence of the language

Consider such question: (Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$. I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
2
votes
2answers
63 views

How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it? Perhaps: SZ shows natural polynomials are equal iff it shows those ...
1
vote
1answer
185 views

Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
5
votes
0answers
89 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 ...
3
votes
1answer
111 views

A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...
0
votes
0answers
22 views

Is $NAAL_{NFA}\in\Bbb{P}$?

$NAAL_{NFA}=\{(a,n)|\;a\text{ is an encoding of a non-deterministic finite automaton without }\epsilon-\text{transitions, }n\text{ is a non-negative integer and }\exists w\in\Sigma^n:\;a\text{ rejects ...