Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,988
questions
-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 ...
- 31
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
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 ...
- 73
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 ...
- 1
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:
...
- 131
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 ...
- 51
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 ...
- 13
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 ...
- 247
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(...
- 211
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 ...
- 11
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]$, ...
- 11
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 ...
- 125
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,...
- 199
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)....
- 469
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? ...
- 4,343
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 ...
- 385
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 ...
- 125
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$, ...
- 247
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 ...
- 247
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 ...
- 247
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 ...
- 247
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 \...
- 121
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 ...
- 247