Questions tagged [decision-problem]

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

-1
votes
0answers
24 views

prove (iMC) i-Max-Clique is NPC

the iMC problem defined as follows: Given graph "G", natural numbers 'k' and 'i' in graph "G" exist 'i' disjointed cliques which are at size 'k'
0
votes
1answer
68 views

Subset with modified condition, is it still NP-complete? [closed]

So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard. The given problem I have is subset sum. However, the conditions have been ...
2
votes
1answer
33 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 ...
0
votes
1answer
164 views

NP hardness of unique Puzzle Generation

Introduction For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The ...
1
vote
1answer
34 views

A question about decidable and undecidable problems

Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem. This is the context: Consider the ...
1
vote
1answer
69 views

3-DNF proves the algorithm is in P class

To understand fully, please read link After, reading the link we will take a look at how we recover our solutions to a constrained Sudoku Puzzle. If we assume that a sudoku puzzle was generated with ...
0
votes
2answers
39 views

Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem. My understanding is that we have to perform a reduction from Hamiltonian Path-...
1
vote
1answer
57 views

Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps. My Thoughts: I am new to proving results like ...
1
vote
2answers
271 views

Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class: \begin{align} C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
1
vote
1answer
78 views

A tricky P=NP problem

Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under ...
0
votes
0answers
46 views

P Langauage to NP Reduction in Polynomial Time [duplicate]

Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings. I tried ...
1
vote
2answers
95 views

Decidable problems for which no concrete decision procedure is known

I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. ...
2
votes
0answers
34 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
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 ...
1
vote
2answers
118 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
82 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
38 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
287 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
293 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
23 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
290 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
104 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 ...
4
votes
1answer
83 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
57 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
13 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
431 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
127 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
23 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
85 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
21 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
46 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
25 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
29 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
299 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
52 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
152 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
61 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
114 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
118 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 ...
2
votes
1answer
257 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
308 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
33 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
88 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
228 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.