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

learn more… | top users | synonyms

1
vote
1answer
29 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
4
votes
0answers
138 views

Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition. A cellular automaton has halted in state $s$ if running the automaton on ...
1
vote
1answer
20 views

restricted sub-permutations check

I am solving the following problem, motived by combinatorial optimization sampling proces. I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) ...
4
votes
0answers
41 views

Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
1
vote
1answer
35 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ...
3
votes
1answer
39 views

Is the word problem for regular languages in ALogTime?

Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word ...
0
votes
0answers
36 views

In computer science, is there a term that describes a solution set that is guaranteed to contain the solution to a NP hard problem?

Suppose that a NP hard problem involves finding a set $A$, and that there exists a polynomial time algorithm that is able to find a smallest set $B$ such that $A \subset B$. Occasionally, we might be ...
5
votes
2answers
121 views

Will encoding affect computability?

I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the ...
1
vote
0answers
40 views

Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
3
votes
1answer
47 views

How do POMDPs and Dynamic Influence Diagrams differ?

To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it). Fully observable ...
6
votes
1answer
59 views

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
11
votes
2answers
794 views

Is Post Correspondence Problem in NP?

I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input ...
7
votes
1answer
113 views

Understanding of Turing's Answer to the Entscheidungsproblem

I apologize if this question has been asked before, but I was not able to find a duplicate. I have just finished reading The Annotated Turing and I am a bit confused. From what I understand, the ...
0
votes
1answer
82 views

Are “TM M accepts some string of length greater than 100” and “TM M accepts some string of length at most 100” decidable?

I have two questions as in the title: TM M accepts some string of length greater than 100 TM M accepts some string of length at most 100 Since 1. is infinite, we can rephrase question as "does TM ...
2
votes
0answers
66 views

Determining whether a number is a perfect square without computing its square root

One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without ...
1
vote
1answer
78 views

Does a path exist going through each color only once?

I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once. I think this problem can ...
6
votes
2answers
159 views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
5
votes
2answers
125 views

How does one find out whether $N = a^b$ for some $b$?

I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form ...
0
votes
0answers
22 views

Computability of $\{y: \text{for some $i$, Turing machine $M$ accepts $y^i$}\}$

Is the set $K = \{y: \text{for some $i$, Turing machine $M$ accepts $y^i$}\}$ decidable or computational enumerable? How to prove this? Attempt: We can write a program to compute $i$th root of ...
1
vote
0answers
70 views

Proving NP-Completeness by reduction

I'm given a more restricted version of 3-SAT called 3-SAT-M: Problem: 3-SAT-M INPUT: A set of clauses C {c1,...,ck} over n boolean variables {x1,...,xn}, where every clause contains ...
1
vote
1answer
79 views

Q: Is chess game movement TM decidable?

If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable? My ...
3
votes
1answer
43 views

Efficient algorithm for determining if $\pm c_1 \pm c_2 \dots \pm c_n = 0$

Suppose that we're given $n$ integers $c_1, c_2, \dots, c_n$. We want to know if there is any assignment of $+$ and $-$ signs such that $$ \pm c_1 \pm c_2 \dots \pm c_n = 0. $$ Does anyone ...
1
vote
0answers
37 views

What are some results for non-trivial lower bounds for the time complexity of decision problems?

Typically decision problems are studied in complexity theory and function problems are studied in the Analysis of Algorithms. Unfortunately, Complexity Theory tends to abstract over the exact time ...
1
vote
2answers
179 views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
2
votes
1answer
98 views

How are these problem variants that ask about the size of optimal solutions in NP?

I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here. On page 5 (23 in the pdf), it says that the following decision problems are in NP: Is the ...
0
votes
1answer
221 views

Clique decision problem restricted to a subgraph [closed]

I know that the clique problem is NP-complete. However, what if we change the problem a little bit? For example, Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are ...
4
votes
0answers
50 views

Proof that P is closed against switching between polynomially related encodings

Lemma 34.1 Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and ...
1
vote
1answer
90 views

NP Complete Subset GCD Proof

$SubsetGCD$ is described by the following: instance: A set of positive integers $S$ and an integer $k$ question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$ ...
2
votes
1answer
82 views

Determine if items can be ordered grouping two simultaneous criteria

For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together. Obviously ...
-1
votes
1answer
73 views

Why decision problem definition ignores Gödel incompleteness theorem?

The following question assume that the decision problem definition (syntactic) has been written (and could be changed if it isn't able) to catch a concept (meaning, semantic) which has both nice ...
3
votes
0answers
59 views

Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
3
votes
1answer
31 views

Extended version of the theory of reals and its decidability

It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
3
votes
4answers
1k views

Language of Turing machines that loop on all inputs, recognizable?

Prove that the language Loop Turning Machine = { < M > | M is a TM that loops on all inputs} is recognizable. I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or ...
1
vote
1answer
195 views

If the decision problem can be solved in poly time, show the optimization problem also can [duplicate]

Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes ...
3
votes
1answer
18 views

Extension of Tarski's result on the decidability of reals

Due to Tarski's result, it is well-known that the first-order theory of reals $(\mathbb{R},+,\cdot,<,=,0,1)$ is decidable. I am working on a paper where I need an extension of this result. More ...
1
vote
1answer
80 views

m-functions in Turing's paper “On Computable Numbers and applications…”

I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem". I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing ...
0
votes
1answer
31 views

Decidable Problem

How should I go about showing that the following problem is decidable: Given DFAs M1 and M2, is L(M1) ⊆ L(M2)? What is the general strategy to prove ...
1
vote
1answer
41 views

Checking if several sets of pairs covers a given set of pairs

Suppose we have $N$ arrays of pairs, e.g. for $N=3$: $A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$, $A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and $A_3 = [ [4,1], [5,1], ...
7
votes
3answers
196 views

Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
-1
votes
1answer
97 views

Restricted version fo CNF-SAT

Given formula $\phi$ on CNF-form in CNF-SAT. Clauses can be arbitrarily long. The problem is NP-complete and it is also given that part of the problem is that a variable can occur many times in a ...
2
votes
1answer
164 views

Why does SAT not reduce to QBF?

So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula) $QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$ So, I guess this is not NP, since solving a ...
1
vote
0answers
23 views

Efficiently decidable logics

So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then ...
2
votes
1answer
96 views

Reduce our problem to a known np-complete problem

Subgraph isomorphism We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$. Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ? (i.e. is there a subset of vertices of $G_2, V \subseteq ...
0
votes
0answers
11 views

Complementation in NP [duplicate]

I understand why complementing $A \in P$, hence $\hat{A} \in P$. I wanted to understand how this would work for problems in $NP$. Is the same valid for NP?
3
votes
2answers
311 views

Algorithm - Wine Bottle Filling

You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 ...
4
votes
1answer
249 views

Does NP-completeness require to find the solution?

In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem: Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$: if ...
1
vote
1answer
92 views

What can I deduce if an NP-complete problem is reducible to its complement?

Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I ...
0
votes
1answer
59 views

Poly-time reduction: D and D Comp [duplicate]

Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function. I will ...
2
votes
1answer
132 views

Is equivalence of a CFG and an RG undecidable?

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?
-1
votes
1answer
52 views

Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...