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,574 questions
-3 votes
0 answers
73 views
Is it valid to compare solving vs checking NP problems using average time per logical step?
I’ve been exploring a measurement approach for NP and NP-complete problems based on average time per logical step. I define: ...
0 votes
0 answers
42 views
Is Exact Matching with more than two colours NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 353
1 vote
1 answer
127 views
Complexity of $Th(\langle \mathbb{Z}; + , 1 \rangle)$ same as $Th(\langle \mathbb{Z}; + \rangle)$?
I want to know a lower bound for the complexity of the decision problem for $\langle \mathbb{Z}; + \rangle$. The below paper notes that Presburger arithmetic, originally $\langle \mathbb{N}; +\rangle$,...
- 277
2 votes
0 answers
25 views
Does the Interior Point Method Solve Klee-Minty Cubes adversarial instances in Polynomial Time?
I am a network engineer currently studying optimization problems. Out of curiosity, I was fascinated by the fact that the Simplex Method has an exponential worst-case complexity, a property famously ...
5 votes
2 answers
651 views
Proof that NP is a subset of EXP
I would like to clarify a misunderstanding I have about the proof that all NP problems can be solved in exponential time. The argument as I understand it is that you can simply test all possible ...
- 319
1 vote
0 answers
113 views
Where is the relativized uniform complementor on r.e. indices stated explicitly (index-operator form)—existence for $\emptyset'$ and any minimality?
Let $\langle W_e : e\in\mathbb{N}\rangle$ be the standard effective enumeration of recursively enumerable (r.e.) sets, where $$ n\in W_e \;\Longleftrightarrow\; \exists s\;\big(\varphi_e(n)\ \text{...
- 31
0 votes
1 answer
49 views
Prove Big Theta for degree p polynomial
Goal Prove that $f(n) = a_pn^p + a_{p-1}n^{p-1} + ... + a_1n + a_0$ is $\Theta(n^p)$ Issue I am having trouble proving $f(n)$ is $\Omega(n^p)$. I know I need a $c_0$ and $k$ such that $f(n) \ge c_0n^p$...
- 35
3 votes
2 answers
185 views
Solving a general 1st order ODE with a series expansion
I am interested in solving the general Cauchy problem: $$\begin{cases}\frac{dx}{dt}=f(x, t) \\ x(t_0)=x_0\end{cases}$$ computationally. Of course, I know there are plenty of well-established methods ...
- 241
6 votes
0 answers
296 views
How does this algorithm "rank" amongst other in the literature?
By merging together the contributions from: a) this answer, b) the comments under this answer, we come up to the following: Claim. For $n\in\mathbb N$, let $Q=(\{1,\dots,n\},*)$ be a quasigroup. Then, ...
- 5,510
4 votes
1 answer
224 views
Subgroup test runtime
In case of a finite subset of a group, the subgroup test boils down to showing that the subset is closed under the group operation. This holds, in particular, for the subsets of a finite group. Q. ...
- 5,510
1 vote
0 answers
54 views
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$. I was reading Expander Graphs and their Applications (Lecture notes for a course by Nati Linial and ...
- 1,811
2 votes
0 answers
182 views
Transitivity check runtime
A necessary condition for a subset $\Sigma\subseteq S_n$ to be a transitive permutation group of order $n$, is to be... transitive. Is the best algorithm to check $\Sigma$'s transitivity faster than ...
- 5,510
2 votes
1 answer
103 views
Polynomial-Time Algorithms for Canonical Form of Ternary Matrices under Row/Column Permutations and Column Negations
We study equivalence classes of ternary matrices of size $m\times n$, where equivalence is defined via row permutations, column permutations, and negation of entire columns. Our goal is to define and ...
- 1,860
0 votes
0 answers
55 views
Can Nested tuples error calculation be improved by using complex numbers?
Hi I am trying to improve my error function . I have some data that is in form of nested tuple. These tuple nesting is base on importance of the data (all the lowest depth data is in as real numbers). ...
- 19
1 vote
0 answers
45 views
Enumerating all "elementary" cycles on a graph
I am interested in enumerating all possible "elementary" cycles of a given graph $G=(V,E)$. What I mean by elementary here, is a notion that I have but am not sure what its called in ...
- 141