Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
28 views

What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
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 \...
-1
votes
1answer
31 views

What does the search problem imply about the decision problem?

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_{...
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
2answers
55 views

A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
6
votes
3answers
916 views

How many decidable decision problems are there?

Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?
0
votes
1answer
76 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 ...
2
votes
2answers
225 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 ...
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 ...
7
votes
3answers
4k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
1
vote
1answer
37 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 ...
1
vote
1answer
17 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 ...
1
vote
1answer
2k views

Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete. The ...
6
votes
2answers
557 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 ...
2
votes
1answer
382 views

4-partition elements summation NP completeness

How can we prove that the following problem $A$ is NP complete? Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
0
votes
2answers
37 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 ...
3
votes
1answer
213 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 ...
3
votes
1answer
117 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 ...
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 ...
0
votes
0answers
42 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 ...
1
vote
2answers
168 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 ...
6
votes
2answers
705 views

Is the $k$P$k$N-3SAT problem NP-complete?

Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$...
0
votes
1answer
52 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 ...
2
votes
1answer
47 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 ...
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
12 views

undecidable problems solvable for humans? [duplicate]

are undecidable problems also unsolvable for humans? I mean I would think I could tell by reading the code of a program if it will halt for a certain input (which would solve the haltingproblem). ...
1
vote
2answers
49 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 ...
1
vote
1answer
110 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 ...
5
votes
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,...
3
votes
1answer
235 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) {...
0
votes
1answer
47 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 $\exists$$SO$ that describe problems with graphs but none ...
2
votes
1answer
101 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 ...
8
votes
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 ...
3
votes
1answer
54 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 ...
0
votes
1answer
81 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 ...
0
votes
1answer
179 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
83 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
85 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 ...
6
votes
3answers
719 views

Does every computational problem have a decision version?

Is the following claim correct?: Every computational problem has a decision version of roughly equal computational difficulty. If the above claim is correct, please give a reference for it. (I ...
0
votes
2answers
78 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
76 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 ...
0
votes
0answers
48 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
309 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
90 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 ...
1
vote
2answers
104 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
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 ...
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
245 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
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
2answers
355 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 ...