Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
15 views

Is there a recursive problem encoding the Turing completeness of a model of computation?

Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
1
vote
1answer
40 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
-2
votes
0answers
27 views

PCP decidable if all words have the same length?

If $X=(x_1,...,x_n) , Y=(y_1,...,y_n)$ with $|x_i|=|y_i|=|x_{i+1}|=|y_{i+1}|=...$ for all $i \leq n$ Is PCP now still undecidable ? I would say it's now decidable because we just have to find some ...
1
vote
0answers
21 views

Decision Making using Multiple Variables

What should I learn if I want to make a decision based on multiple variables? Followings are the example of a problem. I have a farm. My variables are weather, humidity of air, humidity of soil, size ...
0
votes
1answer
41 views

Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
0
votes
0answers
16 views

Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
0
votes
0answers
33 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?
1
vote
2answers
62 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 ...
0
votes
1answer
79 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
239 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
60 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 ...
-1
votes
1answer
32 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
38 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
20 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 ...
6
votes
2answers
565 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 ...
0
votes
2answers
42 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
217 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 ...
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
209 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 ...
0
votes
1answer
56 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
49 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
60 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
59 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 ...
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,...
0
votes
1answer
49 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 ...
3
votes
1answer
383 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) {...
2
votes
1answer
105 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 ...
1
vote
1answer
120 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 ...
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 ...
2
votes
1answer
53 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
183 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
95 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
89 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
87 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
86 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
325 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
92 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
50 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
112 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
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 ...
1
vote
2answers
274 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
90 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
54 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
376 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
644 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
41 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
324 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 ...

1
2 3 4 5
8