# Questions tagged [time-complexity]

Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)

323 questions
Filter by
Sorted by
Tagged with
34 views

### Time complexity of counting the non-prime numbers

So i have a code that i need to find (and proof) the time complexity of it: For ( i = 2 -> N ) For ( j = 2-> sqrt(i)) If(i%j==0) K++ Break; Would really appreciate if someone can help.
1k views

### Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
133 views

### Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$. For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
41 views

### Can a NEXP machine simulate invalid queries to a promise problem oracle?

Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
30 views

### Big O question concerning time complexity

Why is O(f(n)) − O(f(n)) not equal to 0? Full disclosure this is a question from practice problems for my theory class.
40 views

### Find all paths between specially paired nodes in a DAG in linear time

If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a ...
109 views

### Bounds on the construction of regular expressions' intersection operator

There are references on the exponential worst-case of the intersection operator for regular expressions (see ). However, I was wondering if there are similar results for the construction process ...
94 views

### Complexity of acyclicity of a “nondeterministic” graph

By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
2k views

### What are some algorithms where space complexity tends to be the limiting factor in practice?

Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
94 views

### What's the constant coefficient of the Coppersmith-Winograd algorithm?

Every source I can find just says "too big to be practical."
140 views

### Time complexity of Succinct-CVP

I want to know what is the best known lower time complexity of Succinct-CVP? The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of ...
149 views

117 views

### Is 4-in-a-row PSPACE-complete?

This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
154 views

### What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?

I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula. As for the fast algorithms for k-SAT, we see biased-PPSZ, PPSZ, Schöning's local search,...
267 views

328 views

### Given a subset of the hypercube and a copy translated by s, find s

Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...