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

learn more… | top users | synonyms

-2
votes
0answers
39 views

What complexity does the set of all tautologies in predicate logic have?

If we assume $\mathsf{NP} \neq \mathsf{co\text{-}NP}$, is the set of all tautologies in predicate logic NP-complete, in NP but not NP-complete, co-NP-complete or co-NP but not co-NP-complete? I ...
1
vote
1answer
13 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
32 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
68 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
37 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
37 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
16 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
123 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
78 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
52 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
117 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
136 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
63 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
81 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
21 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
76 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
96 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
960 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
243 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
32 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
97 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
151 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. ...
7
votes
0answers
83 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
228 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
86 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 ...
8
votes
0answers
147 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
144 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
191 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
196 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
133 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
115 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
24 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 ...
9
votes
1answer
406 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
78 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
104 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
71 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
223 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
130 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
111 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
147 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
187 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
52 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 ...
3
votes
2answers
89 views

What is a Turing Machine in class coNP

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
9
votes
3answers
265 views

$2k$ number assignment

Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ ...
1
vote
1answer
98 views

Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'

So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that: $M$ halts on all inputs within at most $T(|x|)$ steps If $x$ is in $L$ then $M$ accepts $x$ If $x$ is not in $L$ ...
7
votes
1answer
135 views

Is the universe problem for one-counter automata with restricted alphabet size undecidable?

Consider the following universe problem. The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$. In [1], ...
10
votes
1answer
274 views

Longest cycle contained in two cycles

Is the following problem NP-complete? (I assume yes). Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not ...