Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
-1 votes
0 answers
12 views

Extensions on iOS + Apple maps

Will Apple allow developers to build extensions for there maps app without building a standalone application? I do see documentation about larger companies (Reservation apps, Booking apps, etc.) But I ...
1 vote
1 answer
20 views

Time complexity when implementing uniform family of circuits

It is known that the complexity class P is equivalent to the class of problems decided by polynomial-time uniform familiy of circuits. When stating the complexity of algorithms as this family of ...
  • 111
1 vote
2 answers
54 views

How can we prove that Extract almost minimum operation in a priority queue cannot be done in o(logn)

Given a data structure with 2 operations: insert and extract almost min. Extract almost min operation outputs either the first minimum or a second minimum item from the current structure randomly. How ...
0 votes
1 answer
20 views

How do you specify Big-Theta of an algorithm when the Big-O and Big-Omega are different?

I understand that if f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)), we can conclude that f(n) ∈ Θ(g(n)). ...
  • 1
2 votes
0 answers
21 views

How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?

In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
  • 21
1 vote
0 answers
42 views

Function problem vs decision problem

I am a mathematician novice with the theory of computer science. During the course I took, we dealt with decisional problems (introducing D, SD, coSD classes language side, and P, NP, coNP, EXP, DP, ...
  • 111
-1 votes
1 answer
20 views

what will be the time complexity of the following procedure?

...
  • 1
0 votes
1 answer
22 views

Reducing a known NP-hard problem to a custom 4D planning problem

I'm interested in characterizing the complexity of a decision problem related to path planning. For instance, consider the following problem: Given the current location and battery charge of an ...
  • 103
0 votes
0 answers
60 views

Looking for a book for learning about circuits & arithmetization

Not a computer science engineer but I am a programmer and I also know a very good amount of elementary number theory & abstract algebra. I want to learn about Zero Knowledge SNARKs - I understand ...
0 votes
1 answer
56 views

Set of Turing machines that accepts at least one input in bounded time

What is known about the languages: $$S_f = \{ [M] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|[M]|) \ \text{steps}, \\ \ |x| \leq f(|[M]|) \}$$ I used to think that in ...
  • 155
0 votes
0 answers
16 views

Time complexity of Trie autocompletion (multiple variables in time complexity)

I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
0 votes
2 answers
35 views

translating operations per second (OPS) to floating point operations per second (FLOPS)

I have some algorithmic complexity estimates in Giga Operations Per Second (GOPS) and I would like to compare those with the capabilities of state-of-the-art processors. However, the processor ...
3 votes
3 answers
718 views

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

Why is Solution 1 faster than Solution 2? The input passed to both solutions: ...
0 votes
0 answers
14 views

How to compare two functions which themselves contain additions/subtraction between two functions?

I'm new to Asymptotic Notation and wanted to know how to compare two functions which contain sub functions or contain addition/subtraction of other functions. For example : f(n) v g(n), where f(n) = a(...
1 vote
1 answer
33 views

Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?

I recently saw this answer on a question in the Quantum Computing SE. The answer demonstrated how we can probabilistically find the answer to the Deutsch Jozsa problem on a PTM in $O(1)$ time, with an ...
1 vote
2 answers
49 views

How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"

Issue: I am having a hard time figuring out how to use the worst case for Rolling Hash, especially if the occurrences are only "a and b" for the string. Not only that but it is a bit of a ...
1 vote
0 answers
25 views

Are there EXPTIME-complete problems which are also in IP?

I am wondering if there are known to be any EXPTIME-complete problems (or even just problems in EXPTIME) which are known to also be in IP, so a prover can convince a verifier that an answer to an ...
0 votes
1 answer
39 views

Complexity for optimized k-sum problem

Following up on these two posts Generalised 3SUM (k-SUM) problem? https://people.csail.mit.edu/virgi/6.s078/lecture9.pdf The claim is that k-sum in the general case can be solved in $O(n^{k/2}log(n))$ ...
0 votes
0 answers
8 views

Reduce the independent set problem to the set packing problem

I got this question in my compsci homework and tried the reduction from the solution with an example and it doesn't seem to want to work. Here's the proposed reduction: The independent set problem ...
-3 votes
1 answer
55 views

Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))

How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
  • 1
3 votes
1 answer
52 views

Proof sketch of Blum's Speedup Theorem

In his Quantum Computing Since Democritus, Scott Aaronson outlined a proof sketch of Blum's Speedup Theorem which roughly looks like the following. Given an enumeration of Turing Machines $\{M\}_{i \...
  • 31
-1 votes
1 answer
26 views

Complexity of DFS : O(m)

We say that dfs runs in $O(n+m)$ . For any connected graph $m \geq n-1 $. Therefore : $$m \geq n-1 \implies O(n+m) = O(m)$$ Do you agree ? Because, I have seen in many algorithms proofs this bound $O(...
0 votes
1 answer
28 views

What are some algorithms with runtimes that involve a \log{n} term with a negative exponent?

Are there any (deterministic or randomized) algorithms that run in time $\operatorname{poly}(n)\log^p{n}$ for $p < 0$? What are some examples?
  • 961
1 vote
1 answer
29 views

Give an example of a language $B$ is $NL-complete$ where $B^* \in L$

I need to give an example of a language $B$ is $NL-complete$ where $B^* \in L$. I know $PATH$ is $NL-complete$ (but not limited to using other languages). I am clueless about that. I know $L$ is not ...
1 vote
0 answers
39 views

Regarding constant * opt approximation in agnostic learning

In standard agnostic learning, we assume that there is a concept class $C\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$. Given samples from a distribution $D:\{0,1\}^n\times \{0,1\}\rightarrow [0,1]$, ...
0 votes
0 answers
29 views

How to calculate how many times a function inside a for loop inside a while loop will be called?

I'm studying for my exams and a came through this exercise but I can't prove the result I found. Given this piece of code: ...
0 votes
2 answers
128 views

Why do some "common sense" $P \ne NP$ arguments seem to disregard high-degree polynomials?

I've seen arguments for $P \ne NP$ that rely on certain intuitions about how the real world actually is, generally making the point that it "makes sense" that there exist problems which have ...
0 votes
1 answer
44 views

Is there a notation for boolean algebra complexity?

To represent complexity of an algorithm, Computer Scientist is used to using big-O notation. How about complexity of boolean algebra? Boolean algebra is commonly used in digital circuit design with ...
1 vote
1 answer
31 views

Is ANF-SAT P or NP?

Given a finite set of equations in ANF, for example: $$ \begin{cases} (x_1 \land x_2) \oplus (x_1 \land x_3 \land x_4) \oplus 1 = 0 \\ x_3 \oplus (x_2 \land x_3 \land x_4) = 0 \\ (x_1 \land x_4) \...
  • 13
4 votes
1 answer
50 views

Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?

One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many ...
1 vote
0 answers
23 views

Time complexity of LP problems

In almost all websites and papers, the complexity of LP problem is given in the number of iterations (such as https://or.stackexchange.com/a/5924). I was wondering if there are any references where ...
0 votes
0 answers
24 views

What will be the Computational Complexity in terms of order O of the operations shown in the following figure

Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors. So, first, I have to do a scalar multiplication with a vector ...
0 votes
1 answer
57 views

Enumerate all superincreasing subsequences

A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1,...
3 votes
1 answer
108 views

Find the largest segment within a queried range?

We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$. Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$. ...
2 votes
1 answer
1k views

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
2 votes
0 answers
52 views

Is odd cycles cover NP-complete?

Schaefer proved that deciding even cycles cover ( 2-factor with even cycles) in cubic graphs is NP-complete. I am interested in the complexity of odd cycles cover in cubic graphs. Is it NP-complete? ...
0 votes
1 answer
25 views

Complexity of the feasibility and optimization problems

Given an optimization problem $P$, if we know that this optimization problem is NP-hard, is it necessary to check the complexity of the corresponding feasibility problem, i.e. the complexity of ...
0 votes
1 answer
48 views

Complexity of solving two different LP problems

I have one LP problem (LP1) to solve, where a term in a constraint is to be substituted after solving another LP problem (LP2) (with a different variable vector). Suppose I call the dimension of the ...
1 vote
1 answer
34 views

Is there a hypothesized "complete" class of problems between P and NP-hard?

For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are between complete By between, I mean ...
  • 453
8 votes
3 answers
1k views

Efficient sampling from all positive integers

Let's say we want to find the smallest positive integer x for which some property A holds. We know that such an integer exists. However, we have no knowledge about the scale of x (i.e. x could be 7 or ...
  • 183
2 votes
1 answer
53 views

Are there any problems which are known to be both NP-complete and EXPTIME-complete?

Are there any problems which are known to be both NP-complete and EXPTIME-compelte? My guess is no, because we know that $P$ is not equal to $EXPTIME$ and EXPTIME-complete problems are not in $P$, ...
0 votes
1 answer
26 views

Confusion about NP vs. LINSPACE

I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
1 vote
1 answer
83 views

Why do we need to "allocate" an amount of space in the context of space-complexity?

In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146): It is tempting to say that sub-logarithmic space ...
  • 3,382
1 vote
0 answers
9 views

How branching programs with small width are related to Turing machines with small space?

The complexity book by Arora and Barak mentions that "branching programs of constant width (reminiscent of a TM with O(1) bits of memory) seem inherently weak." I am not able to figure out ...
  • 11
7 votes
1 answer
282 views

Are there superexponential NP-complete problems?

Are there any NP-complete problems where the fastest known algorithm solves the problem in superexponential time (like $O(n!)$ time)? Every NP-complete problem that I am aware of has fastest known ...
3 votes
0 answers
36 views

Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?

I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
  • 153
0 votes
1 answer
23 views

P vs. NP problem and understanding "worst case complexity"

Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
1 vote
1 answer
24 views

construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$

Problem This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell. Assume $L \in {\sf RP \backslash ZPP}$. Define $$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
  • 153
2 votes
0 answers
61 views

Playing with boxes: NP-hard? [Graph Theory]

You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
0 votes
1 answer
38 views

Unpacking the notion of "hardest instances" for NP-complete problems

Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...

1
2 3 4 5
100