Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
0answers
6 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
37 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
420 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
87 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
11 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
47 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
17 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
41 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
20 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
25 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
108 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
18 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
138 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
votes
0answers
13 views

Decide if there exist two vertex set $V_1$ and $V_2$ ($V_1 +V_2 = V$) such that both $V_1$ and $V_2$ are vertex cover

Given a graph $G$ and its vertex set $V$. Considering the following problem: are there two disjoint vertex sets $V_1$ and $V_2$ ( $V_1 \cup V_2 = V$) such that both $V_1$ and $V_2$ are vertex covers ...
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 ...
0
votes
0answers
25 views

Why do we need an opposite machine to prove that Acceptance problem is undecideable?

It is not clear why almost every book uses an opposite Turing machine to get a contradiction. Here in slides they also use the Machine Dwhich simply outputs ...
1
vote
1answer
27 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 ...
-1
votes
0answers
12 views

What is the advantages of decision diagram over decision tree?

while reading few articles I come across few doubts. Could anyone please help me ? The below mentioned are the questions 1)What is the advantage of Decision Diagram over Decision Tree? 2)Is Decision ...
2
votes
1answer
108 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
40 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
votes
0answers
20 views

Formal language vs. decidability problem [duplicate]

What is the difference between a formal language and a decision problem? The formal language definition (which I use) is: subset of Kleene's Hull over an alphabet. The concept of decision problems is ...
1
vote
1answer
95 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
209 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
26 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
79 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
127 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
28 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
32 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
38 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
56 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
109 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 ...
4
votes
0answers
78 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
73 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 ...
1
vote
2answers
135 views

Is it NP complete to decide whether a graph has $k$ disjoint triangles?

I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$ but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in ...
0
votes
0answers
11 views

Explain NP-Hard using an example [duplicate]

I can't grasp the concept of NP-Hard. Basically I have come accross two definitions, summarizing them this is what I understand: Applies the oncept of reducability - Transform problem A to another S, ...
4
votes
4answers
455 views

Are there any optimization problems in P whose decision version is hard?

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
2
votes
0answers
83 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 ...
3
votes
1answer
111 views

Path in a graph with durations

I have the following problem: given a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\...
3
votes
2answers
394 views

What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?

So i came upon this thread : https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable and the guy says Every language in NP is recursive and Every language in NP is ...
2
votes
1answer
46 views

Is deciding if there is a set that is intersected with some given sets and that has at most one common element with other given sets NP-complete?

Given 2 collections of finite sets $A_1,A_2,\ldots,A_m$ and $B_1,B_2,\ldots,B_n$, is there a set $T$ such that: $\left|T \cap A_j\right|\ge 1$, for $j = 1,2,\ldots,m$ and $\left|T \cap B_i\right|\le 1$,...
2
votes
2answers
517 views

Proof that AND-OR graph decision problem is NP-hard

Given an directed acyclic AND-OR graph, where each non-terminal nodes are labelled as either AND or OR. The terminal nodes are the nodes which have no outgoing edges. Children of a node are the ...
1
vote
1answer
92 views

3-Col using each colour exactly $|V|/3$ times

Is the following problem in P? Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times? I believe it is as we are trying to sample three sets (one for each colour) of ...
0
votes
2answers
368 views

Is global non-convex optimization NP-complete?

Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
0
votes
1answer
146 views

If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP

If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP. I am struggling with figuring this out. I know this means Y can be reduced to X, so if I ...