Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

2
votes
0answers
36 views

Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
0
votes
0answers
39 views

Proof of Non-Deterministic Space Hierarchy Theorem

I am trying to prove the Non-Deterministic Space Hierarchy Theorem, which says: If $f$ and $g$ are two functions such that $f=o(g)$ where $g$ is fully space constructible and $g(n) \ge \text {log }n$, ...
1
vote
1answer
34 views

FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?
-1
votes
0answers
24 views

Polynominal Reduction [duplicate]

Given two NP-Complete Problems, there exists a polynominal time reduction from A -> B. Consider: The first problem $$ a^Tx = b, x \geq 0, x \mbox{ integer} $$ The second problem $$ Ax = b, x \geq 0, ...
3
votes
1answer
17 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
-1
votes
0answers
10 views

PSPACE subset of EXPTIME [duplicate]

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. In computational complexity theory, the ...
0
votes
0answers
13 views

Subexponential algorithm for Np-complete problems [duplicate]

http://cstheory.stackexchange.com/a/3627/32204 Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!
4
votes
2answers
149 views

Richard Karp's 21 NP-Hard problems, the meaning of his research?

In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some ...
0
votes
1answer
25 views

Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size." I think that this may be missing a ...
3
votes
1answer
48 views

Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$

I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the ...
3
votes
1answer
24 views

Methods of turning a decision problem into finding the certificate?

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If ...
0
votes
0answers
56 views

3-clique problem is p [closed]

Can we prove that 3-clique P ? Let $G = (V, E)$ be a graph with set of vertices $V$ and set of edges $E$. We enumerate all triples $(u, v, w)$ with vertices $u, v, w\in V$ and $u < v < w$, and ...
-2
votes
0answers
30 views

Bit complexity of modulo operations

Does computing $$a\bmod b$$ require $\Theta(\log a\log b)$ bit operations?
0
votes
1answer
14 views

Polynomial Identity Testing Evaluating a polynomial on a circuit

Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
-3
votes
0answers
44 views

Hamiltonian Tour and one problem [closed]

I ran into a question on previous Mid-Exam. Could anyone clarify something for me? Problem A: Given a complete weighted graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a ...
2
votes
1answer
80 views

Reduction to $n\log n$ time problem

If a problem $A$ is poly-time reducible to a problem $B$ ($A <_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?
0
votes
1answer
34 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
71 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
1answer
68 views

Polynominal reduction from unbounded knapsack problem to general integer programming

Given an oracle that can solve in polynominal time: $$a^Tx=b$$ $$x \geq 0$$ So it can solve the feasibility problem with one equality-constraint(a is here a vector and b is a constant, x is required ...
6
votes
0answers
89 views
+50

Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace ...
2
votes
1answer
23 views

Can we separate P and E?

Let $\mathsf E$ be deterministic exponential time with linear exponent. Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict? If so, what's the proof? The time hierarchy ...
-2
votes
0answers
23 views

If L ∈ NP and L ≤p 3−SAT then L is NP-complete [duplicate]

any expert could help me why this sentence is True? if L∈NP and L≤p3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete.
10
votes
3answers
612 views

Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
4
votes
2answers
99 views

Complexity class of Matrix Inversion

Is inverting a matrix in the Complexity class $\text{P}$ ? From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded ...
0
votes
0answers
25 views

strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practically improvement?
0
votes
2answers
30 views

GCD Strongly Polynominal Time

I don't understand why GCD is not Strongly Polynominal Time? Can you explain in an example, why the storage size cannot be Polynominal Bounded? So is GCD in the Complexity Class P?
4
votes
1answer
39 views

Random Graph is a good expander

If a (n,d) random graph is a n-vertex graph defined as : Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, ...
7
votes
1answer
94 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
1
vote
1answer
34 views

How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle. The proof in [1] makes use of binary ...
3
votes
1answer
215 views

Example of exponential algorithm performing better than a polynomial one?

I have a weird question. I was just wondering if there were some problem with two solutions; one (A) being exponential time, the other one (B) being polynomial time. However the constants involved ...
1
vote
2answers
54 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
0
votes
1answer
30 views

Whats is the meaning of polynomial run-time in input size ? [duplicate]

If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? ...
3
votes
1answer
51 views

FP^NP-complete problems

Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?
1
vote
1answer
34 views

Verifying a solution vs. finding one

There is an algorithmic problem $A(n)$, where $n$ is the size of the problem. It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ ...
2
votes
1answer
38 views

Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states? [closed]

As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can ...
6
votes
1answer
30 views

Versions of NP with different logical unifiers

One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into ...
1
vote
0answers
14 views

Technical clarification on BSS model

In BSS model in which one is allowed $\{+,-,\times\}$ operations, how is division and square root handled? Is there a typical procedure dealing with these involved situations?
6
votes
2answers
104 views

Can element uniqueness be solved in deterministic linear time?

Consider the following problem: Input: lists $X,Y$ of integers Goal: determine whether there exists an integer $x$ that is in both lists. Suppose both lists $X,Y$ are of size $n$. Is there a ...
0
votes
0answers
34 views

Running time of partial algorithms

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
1
vote
1answer
64 views

Artificial intelligence - bridge and torch problem

I am doing a artificial intelligence course as part of my computer science degree. I am stuck on a question about searching. The question is a version of the Bridge and torch problem. Five people ...
2
votes
1answer
19 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
2
votes
1answer
41 views

What is the implication of NP-completeness if P=NP?

If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete ...
5
votes
1answer
63 views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything i have learned recently in Theory of Computation. I was thinking whether combinational ...
1
vote
1answer
39 views

Complexity of Simon's Problem

In reading the Wiki article on Simon's Problem, the article states that it takes exponential time(in the classical version) to discover the secret string S that is inside the black box. Why is this ...
0
votes
1answer
65 views

Is this problem P or NP?

Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$? Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?
-1
votes
1answer
50 views

All optimisation problems have equivalent decision problems

How can we prove the theorem that every optimization problem has an equivalent decision problem, and the optimisation problem is at least as hard as that decision problem? And secondly, I'm not sure ...
2
votes
0answers
38 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
1
vote
0answers
20 views

Real versus Finite field polynomials

Let $f$ be a Boolean function. Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$. Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with ...
0
votes
0answers
14 views

$k$-query oracle Turing machine (Sipser 9.21)

Question: A $k$-query oracle Turing machine is an oracle Turing machine that is permitted to make at most $k$ queries on each input. A $k$-query oracle Turing machine $M$ with an oracle for $A$ is ...
0
votes
0answers
10 views

Solving $Isomorphism$ using $AUTOM$ in polynomial time

Let $Iso$ be the language of all $<G,H>$ such that $G$ and $H$ are isomorphic, and $AUTOM$ be the language of all $G$'s such that $G$ has a non-trivial automorphism. I'd like to show that, ...