# Questions tagged [decision-problem]

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

414 questions
Filter by
Sorted by
Tagged with
84 views

### NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
265 views

### How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
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 ...
44 views

Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time. What does this imply for $\Pi_{... 1answer 39 views ### Is the problem of deciding whether two programs have the same semantics decidable? If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision? This is a question relevant to ... 1answer 38 views ### TM decidable or undecidable problem Problem: Given a TM$M$on the alphabet$\{0,1\}$, determine if there is some input on which$M$executes for at least 5 steps. Is this problem decidable or not? To check if the problem is ... 2answers 599 views ### Are there any proofs of exponential lower bound time complexity I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ... 2answers 93 views ### Decide whether an$n$-bit positive integer is composite Question: Given an$n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP? I know that for every composite number, a factor of the number is a ... 1answer 223 views ### Matrix element value counting in O(1) space The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources. Given an NxM matrix of integer values, we need to verify that the number of non-zero ... 0answers 43 views ### Confusion about P versus NP [duplicate] I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ... 2answers 325 views ### P/NP - Polynomial Reduction vs Certificate I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ... 1answer 75 views ### Decidability of decision problems Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ... 1answer 54 views ### BosonSampling:$\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$implies$P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$I am a complexity beginner, actually a quantum physicist. In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of ... 2answers 76 views ### Complement of languages and coNP By definition, any language (decision problem)$L$is defined as a subset of$\{0,1\}^*$, where$\{0,1\}$is the alphabet.$L^c$is said to be the complement of the language, and it seems to be ... 2answers 2k views ### is FIND WORDS in P? FIND WORDS is the following decision problem: Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left,... 1answer 51 views ### Descriptive complexity of 3SAT lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity. I found many formulas in$\existsSO that describe problems with graphs but none ... 1answer 1k views ### Which languages, decided by a turing machine are decidable? How do I decide if a language is decidable and/or semi-decidable? I have theses languages: a) { < M > | L(M) ⊆ 0*} b) { < M > | L(M) contains at least one word of even length} c) {... 1answer 138 views ### Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following: Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving ... 3answers 3k views ### Show that there are infinitely more problems than we will ever be able to compute I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ... 1answer 145 views ### How to determine if this problem is decidable? I am currently stuck on the following problem: Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times? My ... 1answer 85 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 ... 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 ... 1answer 188 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 ... 1answer 110 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 ... 1answer 96 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 ... 2answers 105 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-... 1answer 111 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 ... 2answers 364 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 ... 1answer 95 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 ... 0answers 61 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 ... 2answers 126 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. ... 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 ... 0answers 14 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 ... 2answers 332 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 ... 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 (... 1answer 70 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 ... 2answers 448 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 ... 1answer 789 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 ... 1answer 43 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 ... 1answer 351 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 ... 2answers 171 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 get the ... 1answer 226 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 ... 0answers 60 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 ... 1answer 106 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 ... 0answers 16 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: ... 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 ... 1answer 47 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 ... 1answer 432 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 ...
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 ...