Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

6
votes
1answer
122 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 ...
0
votes
1answer
15 views

Complexity bound on $RP^{RP}$

This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in ...
0
votes
0answers
28 views

Relationship between functions and formal languages?

PR is defined as "the complexity class of all primitive recursive functions" and also equivalently as "the set of all formal languages that can be decided by such a function". ...
8
votes
1answer
108 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
1
vote
0answers
18 views

On possible existence of OWFs

Assuming $P\neq NP$, is there a computational model in which OWFs cannot exist? What more should we include beyond non-determinism, randomness, quantum model to preclude existence of OWFs?
3
votes
2answers
43 views

Restricted Integer Programming

The integer feasibility problem is NP-complete: $Ax=b, x \geq 0, x \mbox{ integer}$ $A$ contains elements in $\mathbb{R}$ If we restrict this: $A$ contains only elements in: $\{1,0\}$ ...
4
votes
1answer
106 views
+200

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? ...
6
votes
1answer
43 views

Applications of model counting

I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, ...
9
votes
3answers
782 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 ...
-8
votes
2answers
507 views

complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
-3
votes
1answer
78 views

exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

This new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
0
votes
0answers
41 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
35 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?
4
votes
1answer
201 views

For the time hierarchy theorem, how is the input translated efficiently?

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
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 ...
-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, ...
4
votes
2answers
152 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 ...
3
votes
1answer
18 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 ...
5
votes
1answer
162 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
-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!
3
votes
1answer
85 views

Reducing Exact Cover to Subset Sum

Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint: Use ...
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 ...
3
votes
1answer
53 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 ...
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 ...
-2
votes
0answers
30 views

Bit complexity of modulo operations

Does computing $$a\bmod b$$ require $\Theta(\log a\log b)$ bit operations?
2
votes
1answer
81 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
70 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 ...
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 ...
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 ...
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 ...
1
vote
1answer
98 views

Karp reduction from 3-SAT to 3-PARTITION

I want to show that this problem is NP-complete: partition a set of 3n real numbers to n partitions of 3 number which each partition has the same sum of its members. I want to reduce 3-SAT to this ...
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 ...
10
votes
3answers
617 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 ...
-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.
4
votes
2answers
1k views

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
4
votes
2answers
103 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, ...
3
votes
2answers
248 views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

What is the complexity of MIN-2-XOR-SAT and MAX_2-XOR-SAT? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$ where ...
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 ...
3
votes
1answer
216 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 ...
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?
0
votes
0answers
36 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
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)$ ...
1
vote
2answers
103 views

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

I'm so bad at solving the problem of the type: "If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..." That I have to come here and ask these silly questions each and every ...
2
votes
1answer
39 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 ...