Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

3
votes
1answer
23 views

Is Not-STCON is NL-Complete?

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$ I've tried the following proof: Let $S\in NL$, and ...
0
votes
0answers
19 views

Complexity class for loop with two inner loops

I have an algorithm like the following for(int k) { statement1; for(int j) { statement2; } for(int m) { statement3; } } j => ...
2
votes
1answer
108 views

Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
6
votes
1answer
251 views

What is the difference between oblivious and non-oblivious merging, sorting etc

Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?
-2
votes
0answers
17 views

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP? [on hold]

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP ? can someone help me !!
6
votes
1answer
77 views

Is EXPTIME “solvable” or “checkable” in exponential time?

According to this video, EXP has problems that are exponentially difficult to check. But according to this video, EXP are problems that are exponentially difficult to solve. It would make sense to ...
0
votes
0answers
27 views

Complexity of choosing a suitable disjunctive domain for program analysis

Do you know the complexity class of the following problem? Input: A sequential nondeterministic program over integer variables, equipped with initial values of these variables. The exact ...
-1
votes
1answer
30 views

What does permanent in poly time over $\Bbb F_p$ give?

A paper on arXiv [1] states in abstract that permanent of an $n\times n$ matrix over $\Bbb F_p$ in polynomial time gives $NP=RP$. My query is why is 'permanent of an $n\times n$ matrix over $\Bbb ...
0
votes
0answers
32 views

Complexity of choosing a suitable conjunctive domain for program analysis

Do you know the complexity class of the following problem? Input: A sequential nondeterministic program over integer variables, equipped with initial values of these variables. The exact ...
0
votes
0answers
16 views

Complexity of choosing a suitable Boolean algebra domain for program analysis

Do you know the complexity class of the following problem? Input: A sequential non-deterministic program over integer variables, equipped with initial values of these variables. The exact ...
0
votes
0answers
18 views

Complexity of choosing a suitable positive domain for program analysis

Do you know the complexity class of the following problem? Input: A sequential nondeterministic program over integer variables, equipped with initial values of these variables. The exact ...
2
votes
1answer
52 views

Why is the set of perfect squares in P?

I am reading an article by Cook [1]. In it he writes: The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots. I can see how to use Newton's ...
0
votes
1answer
26 views

Are all functions with constant space complexity in $REG$?

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
3
votes
0answers
26 views

How to show that an MINLP with L0 regularization is NP-hard?

I am currently working on a project that involves a mixed-integer non-linear optimization problem, and wondering if I can state that this problem NP-hard in a research paper. I'm not looking for a ...
4
votes
2answers
107 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm is based on the idea that by observing a quantum state, one has to ...
5
votes
2answers
339 views

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says: For all ε‎ > 0, DTIME(O(n)) = DTIME( (1+ε‎‎) n). Now I'm confused with this corollary and ...
3
votes
4answers
620 views

Is there a meaningful difference between $O(1)$ and $O(\log n)$?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
1
vote
0answers
21 views

Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
0
votes
1answer
15 views

How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP. I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N ...
-3
votes
0answers
44 views

Knapsack big O probelm [on hold]

Knapsack problem: Given a set of n items, each with a weight and a value, the problem is to determine the number of these items to include in a knapsack such that the total weight is less than or ...
0
votes
0answers
23 views

Recurrence Equations [duplicate]

How do I write a recurrence equation that describes the running time of the algorithm, then solving that equation to find out the best case Big O? $\bf Algorithm \texttt{ Multiply(A, n)}\\ \bf ...
1
vote
0answers
42 views

Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when ...
2
votes
1answer
102 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
7
votes
2answers
211 views

An one-sentence proof of P ⊆ NP

Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence: It is trivial to show that $\mathbf{P} ...
4
votes
1answer
177 views

Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

$P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results. What is a rigorous proof for $P^{\#P}\subseteq ...
-4
votes
0answers
23 views

Complexity of three subset sum variants [closed]

What is the complexity class of following three problems? (1) Given $n$ integers and another integer $c$ with promise that every subset sum is unique is there a subset that sums to $c$? (2) Given ...
0
votes
0answers
26 views

Proving that $BPP^{BPP}=BPP$

I'm trying to prove that $BPP^{BPP}=BPP$. $BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$.. Can anyone help?
0
votes
1answer
19 views

choose minimum number of M professors in polynomial time in order to design all N course exams

Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N ...
3
votes
1answer
84 views

If graph isomorphism yields a polynomial time algorihtm

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
0
votes
0answers
20 views

If graph isomorphism yields a polynomial time algorihtm [duplicate]

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
3
votes
0answers
61 views

Name for a class of problems solvable in $n^{O(\log \log n)}$

Isomorphism testing of projective planes can be done in $n^{O(\log \log n)}$. This class is contained in quasi-polynomial time. I would like to know more about this class and natural problems in it. ...
1
vote
1answer
30 views

Relation between MAX CUT and MIN CUT

I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)? Barahona, in 1982, showed (Lemma 1) finding a cut ...
1
vote
0answers
144 views

What's a $O(n^2 \log n)$ algorithm that decides if a distinct set is completely triangulable?

Let $P$ be a finite set of $n$ distinct points in $\mathbb{R}^2$. The set $P$ is called completely triangulable if for any three points $p, q, r \in P$ the area of their triangle is always ...
0
votes
0answers
25 views

Reduction of 3-SAT to Vertex Cover?

Can someone explain to me in the most simplest possible way, how to reduce $3-SAT$ to $Vertex\:Cover$ ? I am following the explanation here(scroll to page 4 bottom). I understand the basic setup of ...
0
votes
0answers
16 views

Reduction between parametrized problems

Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers? That is given two parametrized problems whose unparametrized version is $NP$-complete ...
2
votes
1answer
121 views

How can k-means be reduced to Integer Programming

The k-means algorithm reduces to computing the objective function: $ \underset{\textbf{S}}{\operatorname{argmax}} \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i ...
2
votes
1answer
54 views

What is the difference between AM and IP

Intro I am trying to understand how those two models of interactive proof are different. I understand that $\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier) ...
4
votes
1answer
58 views

Complexity of division

The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication ...
14
votes
1answer
377 views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
2
votes
0answers
40 views

Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
6
votes
1answer
148 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
3
votes
0answers
20 views

Cloning the output of a quantum program with unknown input but known measurements

Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to ...
5
votes
1answer
334 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 wondering whether combinational ...
3
votes
1answer
57 views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
2
votes
2answers
132 views

Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_i, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number. ...
-5
votes
0answers
61 views

Big O of NP-Hard problems

If a problem is NP-hard, then can we express its complexity with big O? If yes, what is the big O of NP-hard problems?
5
votes
0answers
115 views

Amortizing or batching circuit evaluation for many different inputs?

Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values ...
3
votes
2answers
75 views

NP problems with exponentially complex average time solution?

Assuming $P \ne NP$, is there a problem such that is NP such that: There is always a solution Alternatively, there is asymptotically almost surely a solution On average, it takes exponential time ...
1
vote
1answer
29 views

Boolean function and real degree

Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$. Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?