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,426 questions
Filter by
Sorted by
Tagged with
46 views

$T(n)=T(n/3)+T(2n/3)+Θ(n)$, find a tight lower bound by substition

I did check for $O(n^3)$ by $$T(k) \leq ck^3-k^2$$for all k<n. It is O(n^3) however checking for O(n^2), can I pick T(k) as $$T(k) \leq ck^2 - k^{1.5}$$ or something like that. Then we can show ...
• 105
29 views

What's the most efficient way to calculate $x' A^{-1} x$, where x is a vector and A is a matrix? [closed]

The expression $\mathbf{x}^T \mathbf{A^{-1} x}$, where $\mathbf{x}$ is a vector and $\mathbf{A}$ is a positive definite matrix, can be solved directly, but I believe I have seen more (computationally) ...
• 103
33 views

Is the assertion that in a probabilistic universe the probability can only approach, and not reach 1 correct? [closed]

P does not Equal NP We can prove this starting with the random oracle hypothesis. “Although the Baker–Gill–Solovay theorem[12] showed that there exists an oracle A such that PA = NPA, subsequent work ...
37 views

Complexity of entailment between equivalences of dual formulas

Consider a propositional language over the set of propositional variables $\{p^+,p^-,q^+,q^-,\ldots\}$ and connectives $\{\wedge,\vee,\rightarrow,\equiv\}$ (conjunction, disjunction, implication, ...
27 views

Proof that checking if a graph has a Hamiltonian cycle is NP-complete

Hi am reading https://www.cs.unm.edu/~saia/classes/362-s08/lec/lec24-2x2.pdf proving that the problem of checking if a graph has a hamiltonian cycle is NP-complete. It uses the fact that the problem ...
39 views

30 views

Maximizing sum of pairwise scores in a set selection problem

I have $n$ sets $A_1$, $A_2$, ..., $A_n$ with $k$ elements each. A score is defined for each pair of elements from different sets. Now consider the procedure of building a new set $B$ with $n$ ...
• 378
24 views

Fast algorithms for computing $AGA^T$ with $G$ PSD symmetric.

Problem: In the context of decision making in some optimization problems, I found that it is meaningful to compute $AGA^T$ with $A\in\mathbb R^{m\times n}$ and $G\in\mathbb R^{n\times n}$ a PSD ...
• 5,944
51 views

Is it possible to find something better than binary search for this problem?

Let's say we have $n$ urns (numbered $1$ through $n$) and the first $k$ urns have a ball in them (for some $k$ unknown to us) and the remaining urns are empty. Our goal is to determine $k$ by looking ...
• 1,338
1 vote
30 views

Designing a DFA with n States for Maximum L* Learning Rounds

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
88 views

Computational Complexity of Equational Logic

Equational logic uses a surprisingly small set of axioms to prove all algebraic identities (algebraic in the sense of universal algebra, so things like field theory fall beyond this scope). This makes ...
• 2,326
33 views

Does for any program it exists a program that is complexitively independant?

So we fix a system turing complet, as the system is fixed it makes sens to speak of complexity with a coefficient like 3t, or 10t² on this system. Let L be all the linear complexity decision problems. ...
67 views

What are a set of example of tasks or problems where the Kolmogorov Complexity is Known -- ideally numerical values can be obtained?

Is there a machine learning task (or any task/problem) that one can by construction know the Kolmogorov Complexity (or minimum description length)? I know the Kolmogorov Complexity is uncomputable but ...
• 6,536
41 views

What is the time complexity of multiplying two matrices over an arbitrary ring?

I know that the time complexity of matrix multiplication over a field is well studied (multiplying two $n \times n$ matrices can be done in $n^\omega$ field operations, where $\omega$ is the matrix ...
• 141
50 views

I'm looking at the Davis-Putnam algorithm. I don't understand how resolution results in an exponential blowup in the size of the formula, since it seems that after each step, the size is reduced. $(... 2 votes 0 answers 45 views Complexity and fast Solution for "probing subset problem"? I have stumbled across a problem in my free time to which I am struggling to find a fast solution to. It came up when solving systems of equations and can be stated as follows: Suppose you have a set$...
For real number search problems, the binary search algorithm is the go-to method. Yet, the answer becomes not so obvious when considering searching for some number $x$ such that $|x-Z_0|\leq R$. I ...