# Tagged Questions

Questions related to the (computational) complexity of solving problems

1answer
181 views

### How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
0answers
18 views

### Complexity of Self avoiding walks in unary

In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and ...
2answers
51 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 ...
1answer
84 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 ...
0answers
27 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 => ...
1answer
301 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?
1answer
103 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 ...
0answers
21 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 ...
0answers
21 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 ...
0answers
36 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 ...
1answer
29 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$?
1answer
63 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 ...
0answers
30 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 ...
0answers
22 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 ...
2answers
344 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 ...
1answer
33 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 ...
6answers
771 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}$ ...
0answers
23 views

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 ...
0answers
62 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. ...
1answer
32 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 ...
0answers
44 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 ...
0answers
17 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 ...
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 ...
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) ...
1answer
68 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 ...
1answer
27 views

### Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?

Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10? for example ...
0answers
42 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 ...
0answers
41 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 ...
2answers
134 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. ...
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)) = O(n)$...
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$?
2answers
78 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 ...
1answer
64 views

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 ...
0answers
104 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 ...
0answers
117 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 ...
1answer
49 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"): https://en.wikipedia.org/wiki/Category:NL-...
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 P^{PP}$...
1answer
81 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 ...
1answer
53 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 ...
1answer
112 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?
0answers
47 views

### Why is $coNP\subseteq NP/O(1)$ and $coNP\subseteq NP/O(\log n)$ not same as $coNP=NP$?

If $NP\subseteq P/log\implies P=NP$ why does $coNP\subseteq NP/O(1)$ or $coNP\subseteq NP/O(\log n)$ not implies $coNP=NP$?
1answer
31 views

### Heavy hitters problem linear scan and auxiliary space

I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem: We have an array of $n$ elements and we want to know which ...