Questions tagged [computational-complexity]
Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.
3,471
questions
0
votes
0
answers
19
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:https://dl.acm.org/doi/pdf/10.1145/62212.62241, what's given is $P(x)$ a (sparse) multivariate polynomial with real(or complex) coefficients.
The author claimed two things.
It is known ...
- 61
1
vote
0
answers
29
views
Is this generalization of determinant for a higher-order tensor a standard object?
The determinant of an $n$ by $n$ matrix $a$ can be defined as
$$ \mathrm{det}(a)= \sum_{\sigma} \mathrm{sgn}(\sigma) a_{1,\sigma(1)} a_{2,\sigma(2)} \dots a_{n,\sigma(n)}$$
where $\sigma$ is a ...
- 31
6
votes
1
answer
100
views
Why does "The Twelve Days of Christmas" have space complexity O(sqrt(n/log n))?
I've been reading Donald Knuth's "The Complexity of Songs", a "joke" paper about the space complexity of certain songs' lyrics (here's a link), for a bit of informal research. ...
0
votes
0
answers
49
views
Is there a propositional proof system that is not known to be simulated by extended Frege? [closed]
Extended Frege is a propositional proof system that is achieved by adding the extension rule to a Frege system. That rule allows to replace formulas with fresh variables.
A propositional proof system $...
- 411
0
votes
1
answer
63
views
Find the dominating term
I know that, $$a+b=\Theta(\max\{a, b\}).$$
I need to understand the dominating term in this expression,
$$\mathcal{O}(m^{\frac{2}{3}}n^{\frac{2}{3}}+m+n).$$
We know that,$$m^{\frac{2}{3}}n^{\frac{2}{...
- 298
-1
votes
0
answers
32
views
Fixed quantities in Big O notation
Consider the following description of a random graph generation algorithm with parameters $n$ (number of vertices) and $m$ (number of edges).
All iterations add an edge except those where a ...
- 3,468
1
vote
0
answers
67
views
What does "any polynomial dominates any logarithm" mean here?
My textbook states that
any polynomial dominates any logarithm: $n$ dominates $(\log n)^3$. This also means, for example, that $n^2$ dominates $n\log n$
However, it wasn't clear to me what the ...
- 3,019
0
votes
0
answers
36
views
How to bound depth of communication with nondeterministic communication complexity and rank
In Kushilevitz and Nisan, there is an exercise which asks you to prove the following:
$D(f)=O(N^0(f)\text{log rank} (f))$.
Here, $D(f)$ is the depth of the most efficient two party communication ...
- 1
0
votes
0
answers
37
views
Proving there exist $g,h$ where $g = \Theta(h)$ and $f(x) = g(x) - h(x)$ for a function $f$
I am trying to prove that for any function $f : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$, there exist $2$ functions $g : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$ and $h : \mathbb{Z}^{+}\rightarrow \...
- 3,019
0
votes
1
answer
54
views
Proving $f + c = O(f)$ doesn't always hold- where is my mistake?
I seem to have proved the following statement false: that for any function $f : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$ and any $c \in \mathbb{R}, f +c = O(f)$, where for any $2$ functions $f : \...
- 3,019
11
votes
0
answers
164
views
What is the current best algorithm to find if a simply connected region is uniquely tileable with dominoes?
I was reading both Thurston's and Fournier's papers on algorithms which detect whether or not a simply connected region is tileable using dominoes (1 by 2 rectangles) when I came across the section in ...
- 425
1
vote
1
answer
23
views
Relationship between relative PA degree and Turing reducibility.
According to Reverse Mathematics, Definition 2.8.24 by Dzhafarov–Mummert, we say that a function $f \in 2^\omega$ has PA degree relative to $g \in 2^\omega$ if the collection of $f$-computable ...
- 104
0
votes
1
answer
49
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,468
0
votes
0
answers
11
views
Relative running times of equivalent Turing machines with arbitrary and binary alphabets
Cross posted from CS Stackexchange as no answers were found there. If it is found inappropriate for this site I will remove it.
The book "Computational Complexity: A modern approach" by ...
- 469
8
votes
4
answers
706
views
How to Find Efficient Algorithms for Mathematical Functions?
Context: I had to write a code that would compute $\arctan(x)$ for all real $x$ with an error less than $10^{-6}$. The only algorithm I could think of was using the Taylor series of $\arctan(x)$, ...
- 6,618