Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (1)

4
votes
1answer
35 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.
0
votes
1answer
20 views

Maximum number of configurations on a TM that decides the language $A_\text{NFA}$

Consider a Turing Machine $M$ that decides the following language: $$A_{\text{NFA}} = \{ \langle N,w \rangle | N\text{ is an NFA and }N\text{ accepts }w \}.$$ Based on its input size, if $M$ wants to ...
3
votes
2answers
33 views

Fast algorithm to find points on one side of hyperplane?

Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm (1) Preparation: first take the n points as an input, ...
1
vote
2answers
42 views

Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

Let the following datatype be defined: data T = A | B T | C T T That is, B, B T, B (B T), C A A, C (B T) A and so on all are ...
1
vote
1answer
20 views

Is Simon's problem a good NP-intermediate candidate?

We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$ (Though we have the proof that BQP $!=$ BPP with an oracle) Since Simon's problem (as factoring) it's easily solvable by a ...
2
votes
1answer
50 views

Why is the Boolean hierarchy contained in the class $P^{NP}$?

My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P_2\cap\Pi^P_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince ...
0
votes
1answer
28 views

Complexity of general polynomial map evaluation is polynomial?

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x ...
4
votes
2answers
181 views

Time complexity of base conversion

EDIT As requested, a single question Why can't arbitrary base conversion be done as fast as converting from base $b$ to base $b^k$ ? There is a big time complexity difference, so I am also ...
1
vote
0answers
7 views

Question about Kannan's theorem [migrated]

I was reading a paper of Buhrman and Homer "Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy" ...
12
votes
0answers
570 views
+100

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
0
votes
0answers
20 views

Reduction from 3 Dimensional Matching to Magnets [on hold]

http://imgur.com/gw31LLH To elaborate a bit on MAGNETS. Imagine you have a pile of fridge magnets M and a list of words that can be spelled with the magnets called W. Given a set of magnets M and a ...
55
votes
5answers
10k views

In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that np is a subset of np complete which is a subset of np hard... but I have no idea ...
3
votes
2answers
273 views

Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
9
votes
3answers
654 views

Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
4
votes
1answer
158 views

Is building this tournament fixture an NP-Hard / NP-Complete problem?

I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it. I have written a program which randomly ...
0
votes
3answers
41 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 ...
2
votes
1answer
56 views

Partitioning NP-complete problems

Let's suppose I have an NP-complete problem A. Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete? My guess would be yes. ...
1
vote
1answer
59 views

3-SAT to Max-2-SAT Reduction

I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck. Let me first describe it. 3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in ...
2
votes
2answers
90 views

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
2
votes
1answer
99 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
3
votes
2answers
268 views

How to determine if a black-box is polynomial or exponential

I have a problem which essentially reduces to this: You have a black-box function that accepts inputs of length $n$. You can measure the amount of time the function takes to return the answer, but ...
0
votes
0answers
19 views

Cyclic definition of NP-completeness [duplicate]

Trying to understand the concept of NP-completeness, I came across this pearl on Wikipedia: From NP-complete: A decision problem L is NP-complete if it is in the set of NP problems and also ...
2
votes
2answers
46 views

Is summing over all possible $k$-combinations NP-hard?

Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ \sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c ...
1
vote
1answer
51 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality [closed]

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
1
vote
1answer
45 views

Showing that DNF VALID is coNP-hard

I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), ...
0
votes
1answer
34 views

NP Problem definition – verifiable on DFA vs. solvable on NFA

So in complexity theory, I've run across different definitions for NP problems -- Decision problems where a solution can be verified by a DFA in polynomial time Decision problems where a solution ...
1
vote
0answers
16 views

Is it possible for n = poly(Omega(n))? [closed]

Just wondering, if it were possible to have n = poly(m) and then would m = Omega(n) be valid?
5
votes
1answer
104 views

NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
6
votes
2answers
137 views

If $\log xy=\log x+\log y$ then why multiplication is harder than addition?

Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this ...
1
vote
1answer
66 views

Traveling Salesman: how to use a lower bound?

Let me preface this question by giving some helpful background material. I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
-1
votes
1answer
26 views

3SAT to CNF-SAT reduction

I am trying to prove that 3SAT is polynome time reducable to CNF-SAT, but I don't know how to do this. A formula F is in 3SAT iff f(F) is in KNFSAT, but since 3SAT is a part of KNFSAT, every formula ...
-1
votes
0answers
27 views

What is the Unique Games Conjecture? [closed]

What is the unique game conjecture in relatively simple words? What are the consequences of proving it or disproving it? Does it has any relation to game theory? Why is there "game" in the name?
-1
votes
0answers
17 views

pebbling is DSPACE($O(n^2)$) [closed]

Given a DAG $G$ and a vertex $v$ , consider the following game: We can place a pebble on a vertex $u$ if all its predecessors have pebbles on them. We can remove a pebble from a vertex any time. The ...
3
votes
1answer
35 views

grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are ...
10
votes
2answers
574 views

Decision problems in $\mathsf{P}$ without fast algorithms

What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known ...
4
votes
1answer
25 views

Counting approximate solutions

Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the ...
6
votes
1answer
33 views

Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight

There is a basic result in circuit complexity that says: There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$. The argument is a simple counting argument on the ...
2
votes
2answers
66 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
55 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 ...
2
votes
0answers
31 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
1
vote
0answers
47 views

Clique and PSPACE [closed]

I was wondering how I could go about creating an algorithm that gets all the cliques in a graph in PSPACE So far, based on some of the readings I've done, I am considering to use bit-strings (that ...
5
votes
1answer
84 views

How to compare algorithms in class NC time complexity with other classes?

I know these relations : \begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i ...
5
votes
4answers
121 views

Can all NP-complete cryptosystems be broken if one is broken?

I was just reading something about NP-hard problems and cryptosystems. I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) ...
5
votes
0answers
49 views

Reduction from clique to bag automata

I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem: Bag Automaton: A non deterministic finite state automaton ...
1
vote
2answers
81 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
7
votes
1answer
215 views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
2
votes
1answer
24 views

Polynomial hierarchy intersection

While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} ...
2
votes
1answer
33 views

Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
1
vote
2answers
71 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 ...
2
votes
2answers
149 views

Which NPC problems are NP Hard [duplicate]

I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete And Wikipedia defines this as ...