Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

2
votes
2answers
30 views

How do you prove that polynomial reductions are not symmetric?

How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other ...
3
votes
1answer
72 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
25 views

Complexity class for loop with two inner loops [duplicate]

I have an algorithm like the following for(int k) { statement1; for(int j) { statement2; } for(int m) { statement3; } } j => ...
6
votes
1answer
269 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
89 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
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 ...
-1
votes
0answers
35 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
29 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 ...
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$?
-1
votes
1answer
31 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 ...
2
votes
1answer
55 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 ...
3
votes
0answers
27 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 ...
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 ...
5
votes
2answers
342 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 ...
0
votes
1answer
16 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
47 views

Knapsack big O probelm [closed]

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 ...
3
votes
4answers
625 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}$ ...
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 ...
-3
votes
0answers
23 views
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 ...
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?
7
votes
2answers
213 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} ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2
votes
2answers
133 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?
4
votes
2answers
91 views

What are some “easy” unreasonable implications of O(1) time memory access?

If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take $O(\mathbf{log}(N)) = ...
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$?
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 ...
4
votes
1answer
60 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is ...
0
votes
0answers
47 views

How do you reduce graph edge colouring problem to the graph node colouring problem

I know that if the nodes of a graph can be coloured by $n$ colours such that no two nodes sharing an edge have the same colour, I can also colour its edges with $n$ colours such that no two different ...
2
votes
1answer
47 views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length ...
0
votes
0answers
20 views

On Karp reduction

Assume a complete problem for a class $\mathcal C$ is in $P/poly$ and at each $n$ assume that the advice string is $s_n$ of length $n^c$ for a fixed $c>0$. Assume that $SAT$ of $n$ length input ...
4
votes
0answers
84 views

Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
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 ...
2
votes
1answer
44 views

What are examples of $\mathsf{NL}$-complete problems?

Wikipedia lists exactly two problems as $\mathsf{NL}$-complete - 2-satisfiability and St-connectivity (although stating that there are "several"): ...
4
votes
1answer
179 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 ...
2
votes
1answer
77 views

Is it possible that $\mathsf{L} = \mathsf{NP}$?

When I studied computer science 10 years ago, it was still an open question whether $\mathsf{L}$ and $\mathsf{NP}$ are truly different classes. Is that still the case or has the inequality been proven ...
1
vote
1answer
50 views

Turing NP complete but not Karp NP complete?

Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction? Conversely is there some examples of candidate problems that have Turing reduction to SAT ...
2
votes
1answer
110 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?