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

learn more… | top users | synonyms

0
votes
1answer
64 views

Clique Decision Problem? [on hold]

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), and k-integer, we are given a decision problem to find a ...
3
votes
0answers
34 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
49 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
2answers
68 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
44 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
41 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
27 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
443 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
142 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
15 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
52 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
23 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
38 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
178 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
83 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
119 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
18 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
82 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
263 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
246 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
76 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
52 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
116 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
50 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 ...
2
votes
1answer
17 views

Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
0
votes
1answer
40 views

Not Hamiltonian is in NP Class? [duplicate]

I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest. From this book and other study in complexity theory, I have seen the following ...
2
votes
1answer
85 views

Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
0
votes
0answers
18 views

General methods for polynomial reductions? [duplicate]

Let's say you want to show $A \leq_{p} B$ (this is usually in the context of showing $B$ is NP-complete, but I'm just asking about the reductions. We are specifically looking at polynomial (Karp) ...
0
votes
1answer
57 views

How does the ID3 Algorithm differ from a generic Decision Tree learning algorithm

Based on the notes of my Machine Learning lecturer, I am struggling to understand how the two algorithms differ? Both seem to select the most informative feature A (based on least entropy), then ...
8
votes
0answers
98 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
2
votes
0answers
30 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
2
votes
1answer
103 views

Find a subgraph whose edge weights sum to at least the number of nodes

Given a graph G = (V,E) every edge is assigned a real number Xe $\in$ [0,1] The sum of x variables for all edges is equal to the number of edges -1 : $\sum x_V = |V|-1$ For a subset S ...
0
votes
1answer
41 views

Decide $\{a^nb^n\mid n>0\}$ in log space

Given $S = \{a^n b^n \mid n > 0\}$, show $S$ is deterministically decidable in log space. Hint: to count up to $n$ you need $\log n$ bits. This comes from some lecture notes at ...
1
vote
2answers
31 views

Can all decision problems reduce to undecidable?

If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this? Or did I just misunderstood the idea of reduction?
-2
votes
3answers
214 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
1
vote
1answer
102 views

Can a solvable problem be encoded in a recursively enumerable language?

Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new ...
-1
votes
1answer
41 views

Why apply the assumed decide für HALT to the input and its code?

In the lecture notes I have got in class I have the following proof for the halting problem not being recursive Assume $H$ is recursive and TM $M_1$ decides it. Construct $M_2$ that gets ...
3
votes
0answers
80 views

I need a better data structure than a graph with condition nodes

Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of ...
10
votes
1answer
356 views

Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
2
votes
1answer
33 views

Property of two ANEAs is in NP

I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by ...
-1
votes
2answers
40 views

What is decision version of integer programming

I dont know what is meant by decision version of Integer Programming. I know ILP, but this terminology has me confused. There are no good resources on Google.
1
vote
1answer
40 views

Integer Linear Programs: An instance or not?

Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is ...
2
votes
0answers
89 views

Is this modification of the subset-sum problem NP-complete?

Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, ...
1
vote
1answer
168 views

When is splitting a collection coins two ways NP-complete?

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ...
2
votes
1answer
66 views

how to prove a language is decidable

Hopefully this is not a duplicate How do I prove a Language L={a,b,c} is decidable or not I read somewhere that if a turing machine accepts a language and halts on every input string then the ...
3
votes
1answer
500 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
151 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 ...
-3
votes
1answer
70 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
96 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$. ...