# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,988 questions
Filter by
Sorted by
Tagged with
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
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
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 ...
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)). ...
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
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
20 views

...
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
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 ...
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
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 ...
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 ...
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: ...
• 131
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
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
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
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 ...
• 247
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))$ ...
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 ...
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
52 views

• 211
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
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
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]$, ...
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: ...
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 ...
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
31 views

• 153