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

learn more… | top users | synonyms

3
votes
1answer
79 views

Non-deterministic Turing machine and palindromes

I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$. I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – ...
2
votes
2answers
102 views

Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
-4
votes
1answer
45 views

Determine if DFAs accept any word which contains bb [closed]

Let $\Sigma=\{a,b,c\}$. Describe an algorithm that takes as input a deterministic finite automaton $M= (Q,\Sigma,\tau,s,A)$ and determines whether or not $M$ accepts a word containing $bb$ (i.e., a ...
1
vote
2answers
68 views

NP-hardness of an optimization problem with real value

I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$. ...
1
vote
1answer
55 views

Feasible solution existence

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty. Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is ...
6
votes
1answer
69 views

Is Post's Correspondence Problem decidable with fixed word size?

So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$. I'm wondering, can anything similar be said for when there is a fixed word length? To be precise, here's ...
1
vote
1answer
15 views

Paths between tuples, MSV, decision trees

I'm reading about Multiset Size Verification Problem and in the following paper - http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_2.pdf - I got stuck just on the first lemma. However, ...
2
votes
1answer
35 views

A variant of the set cover problem: Is that a known problem?

Can this problem be solved in poly time? Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$. Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that ...
1
vote
1answer
69 views

Decision Tree and rank?

Consider all strictly decreasing functions from {1,2,3,4} to {1,2,3,4,5,6}, or in other words, all functions defined on {1,2,3,4} such that f(1)>f(2)>f(3)>f(4). Draw a decision tree so that the leaves ...
2
votes
1answer
43 views

Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$. Is answering to that problem yes or no equivalent to subset-sum problem? What would ...
1
vote
1answer
39 views

Can This Property (Representative Property) Be Generalized?

I recently came across with a question that asks for the greatest subset of a given set, which includes relatively prime elements.(Randomly selected item from a set is always relatively prime to all ...
0
votes
0answers
18 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
7
votes
1answer
129 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
6
votes
2answers
89 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
0
votes
3answers
59 views

Constraints on subset sum problem [closed]

Subset sum is given by this question: "The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?" My question is: If the numbers in the set are ...
1
vote
1answer
118 views

Algorithm to decide if $n \le m!$

This is an assignment of an introductory course of complexity theory and I need to find a way to do the following: Given $n,m \in \Bbb N$, is $n \le m!$ ? The idea is to provide a Post Machine that ...
1
vote
3answers
141 views

Why is SAT in NP?

I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?
0
votes
1answer
67 views

Proof of P ⊆ NP [duplicate]

What is the proof of P ⊆ NP? I cannot happen to find a good explanation for it. I read that the verifier will just ignore the proof and accept any proof if the ...
1
vote
2answers
90 views

Is subset sum with a fixed target sum NP-complete?

I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a constant number? So the decision problem would look like this: Input: A collection of ...
0
votes
0answers
11 views

two undecidable languages with a decidable union/intersection? [duplicate]

does there exist two undecidable languages such that their union is decidable? what about a decidable intersection? One thing that I've been trying to figure out is if J and K are both undecidable ...
1
vote
1answer
28 views

Doubt in the correctness of decision tree models for constructing a lower bound

If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$. But with the decision tree model, the number of leafs is ...
2
votes
1answer
80 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
3
votes
1answer
98 views

Digraph problem relating in- and out-degrees

Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d_{D'}^+(u) \leq d_{D'}^-(v)$ holds for every arc $(u, ...
2
votes
2answers
1k views

Detecting a subsequence that's an arithmetic progression, in a sorted sequence

I have following problem: I have a sorted sequence of $N$ integers (assume they are monotonically increasing). I want to check whether there is any subsequence of length $\ge N/4$, such that ...
0
votes
3answers
287 views

Turing machine that accepts language with more a's than b's

I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think ...
-1
votes
1answer
35 views

Decision Problem Algorithm

I have a question: Every Decision problem has a method, turing machine or algorithm to solve it? If the answer is not, Could show me any example?
3
votes
1answer
98 views

“Unusual” coupling between a decision problem and a corresponding optimization problem

There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case? Are there examples where the typical ...
0
votes
0answers
29 views

Why NP is not closed under complement? [duplicate]

Please correct my statement. Assuming $L\in NP$, and algorithm A can determine L in poly-time in a nondeterministic machine, we have algorithm $A'$ and the complement of $L$ -- $L'$. $x$ is the input ...
3
votes
1answer
156 views

Is membership of x in an infinite set decidable?

In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. ...
6
votes
0answers
93 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
8
votes
1answer
235 views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in ...
1
vote
1answer
88 views

Prove that <Z> is not a element of NOT-SELF

I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster. Suppose we have $$\text{NOT-SELF}=\{\langle M\rangle \mid M ...
10
votes
1answer
220 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 ...
4
votes
1answer
147 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 ...
7
votes
1answer
196 views

Complexity of (SAT to 3-SAT) Problem?

It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible ...
5
votes
2answers
204 views

3-SAT where variables occur equally many times as a positive literal and as a negative literal

Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$. Is it ...
7
votes
1answer
134 views

Complexity of Monotone (+,2) SAT problem?

To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem: Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF ...
6
votes
1answer
116 views

Complexity of deciding the satisfiability of a quasi-monotone CNF formula

A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal). What is the complexity of deciding its ...
3
votes
1answer
45 views

Undecidability of the PCP problem with bounded width

Given two ordered sets of words $a_1, a_2, ..., a_k$, $b_1, b_2, ..., b_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i_1, ..., i_n$ taking values in $1, ...
1
vote
0answers
25 views

Relevant subtree and relevant leaf in Machine Learning Decision Trees

I'm currently studying Decision Trees and the definition of a decision tree in our course is somewhat obscure for me. Nowhere in other online definitions of decision trees do I find something about ...
10
votes
1answer
505 views

Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

Those terminologies confuse me. As I understand SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search). Decision procedure is a procedure to decide the ...
1
vote
0answers
90 views

Does FNP-complete = NP-complete?

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong. So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
5
votes
1answer
107 views

One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP

Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$. But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using ...
0
votes
1answer
72 views

Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch". With "from scratch" I mean that it does not use some other undecidable problem to ...
0
votes
1answer
267 views

Showing that CLIQUE can be verified in polynomial time

The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is in NP and there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in ...
1
vote
1answer
153 views

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve. Any hints (not answers) from which side to attack it? Let ...
3
votes
2answers
112 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
4
votes
1answer
150 views

Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$. How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?
6
votes
3answers
195 views

Computer science problems related to music?

Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
3
votes
0answers
55 views

Online algorithm for planning

Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A ...