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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
mark's user avatar
  • 105
-1 votes
0 answers
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) ...
duckmayr's user avatar
  • 103
-2 votes
0 answers
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 ...
gggggggggggg's user avatar
0 votes
0 answers
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, ...
Daniil Kozhemiachenko's user avatar
0 votes
0 answers
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 ...
Keven McFlurry's user avatar
0 votes
0 answers
39 views

Efficiently calculating the inverse of a matrix $A+D$, where $A^{-1}$ is known and D is diagonal with few non-zero points

Lets say I have a $(N,N)$ matrix $A$ and want to quickly calculate the inverse of an updated matrix $A' = A+D$, where $D$ is a diagonal matrix with only a few non-zero entries with positions $M = \{...
j bloggs's user avatar
0 votes
0 answers
23 views

solving 3_sat using system of polynomial equations in gf2

Any single variable polynomial in $GF(2)$ is reduced to first degree $x^n=x$. So all polynomials of $n$ variables will be like $x+y+xy$ We can transform any 3-SAT as a system of polynomial equations ...
Mohamed Hamlil's user avatar
0 votes
0 answers
17 views

Complexity of symbolic computation of matrix inverse?

I am an engineer who is working with some linear equation problems. In my application, I found out that in having the symbolic form of such matrix inverse actually speed things up (for example ${A^{ - ...
Tuong Nguyen Minh's user avatar
-2 votes
0 answers
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$ ...
learner's user avatar
  • 378
0 votes
1 answer
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 ...
P. Quinton's user avatar
  • 5,944
2 votes
1 answer
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 ...
user23571113's user avatar
  • 1,338
1 vote
0 answers
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 ) ...
Coping Forever's user avatar
2 votes
1 answer
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 ...
Thomas Anton's user avatar
  • 2,326
0 votes
0 answers
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. ...
Guill Guill's user avatar
0 votes
1 answer
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 ...
Charlie Parker's user avatar
2 votes
1 answer
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 ...
GHPR's user avatar
  • 141
0 votes
1 answer
50 views

Resolution Exponential Memory Blowup

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. $(...
David Cheung's user avatar
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 $...
Sese Mueller's user avatar
0 votes
0 answers
29 views

best search method in the complex plane

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 ...
ironmanaudi's user avatar
1 vote
1 answer
43 views

Big O complexity of $T(n)=2T(n/2)+\log(n)$

I am trying to evaluate the Big $O$ complexity of $T(n)=2T(n/2)+\log(n)$. I've tried approaching it using Telescopic sum, and arrived at the following: $$T(n)=2^{k}T\left(\frac{n}{2^{k}}\right)+\sum_{...
Paras Khosla's user avatar
  • 6,481
0 votes
1 answer
43 views

Does finding feasible solution to set cover problem is as hard as SAT problem?

I have a weird feeling that finding a single feasible solution to the set cover problem is as hard as SAT problem. I think that this might be wrong but I am not sure why. To illustrate my thinking, ...
Tuong Nguyen Minh's user avatar
2 votes
1 answer
355 views

How to prove that the following simplification rule is satisfiability-equivalent?

Denote $F\overset{\text{SAT}}{\equiv}G$ if $F \in SAT {\iff} G \in SAT$. A transformation of formulas $S(·)$ is called satisfiability-equivalent if $\forall{F}\space F\overset{\text{SAT}}{\equiv}S(F)$....
S. M.'s user avatar
  • 1
0 votes
1 answer
52 views

Why is the time complexity of checking parity of integer $O(1)$?

Can someone please explain why "checking a bit" is $O(1)$? In our class, we were only told the number of binary operations for multiplications and additions between two integers so I don't ...
Jason Xu's user avatar
  • 547
0 votes
1 answer
106 views

Polynomial Algorithm for checking if graph is Weisfeiler Leman isomorphism test counterexample

I am currently working on isomorphism tests between graphs, however. Is there a polynomial algorithm for determining whether a graph is a potential 1-WL counterexample? By counterexample I mean graphs ...
Eauriel's user avatar
2 votes
1 answer
62 views

What's wrong with this argument? Determining satisfiability of CNF

I am working with the following definition of the conjunctive normal form of a propositional formula: A formula $\phi$ with propositional variables $P_1 \ldots P_n$ is said to be in conjunctive normal ...
rea_burn42's user avatar
1 vote
0 answers
74 views

Fundamental Axiom of Floating Point Arithmetic for Complex Numbers Multiplication

I am trying to prove the fundamental axiom of floating point arithmetic also applies to complex number multiplication. First, let $fl$ be a function that maps a number to its closest floating point ...
Gu Bochao's user avatar
-2 votes
2 answers
68 views

Does the idea of creating a perfectly random problem to solve this have any merit, or is it completely useless quackery? [closed]

Statement- If perfect random proves P cannot equal NP Explanation- The crux of P = NP is not figuring out the answer, but rather proving it, and the mathematical community has been approaching this ...
ChadTheVlad's user avatar
2 votes
0 answers
49 views

Positive boolean satisfiability problem : finding minimal solutions.

Consider, over a finite set of boolean variables X, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals. For every assignment of the variables which ...
Christopher-Lloyd Simon's user avatar
2 votes
0 answers
85 views

Any relations between numbers representation in different bases?

Is there any other way than just converting numbers between bases, to find out if a given number of one base represented in another arbitrary base is going to have certain count of unique digits? I ...
streamofstars's user avatar
2 votes
2 answers
71 views

Why is computing powers in modular arithmetic $O(2^k)$?

How do they get the exponential time claim? Is this a mistake in my lecture notes? I am told that to multiply two k-bit integers roughly takes $≤2k^2$ bit operations; thus shouldn't $b-1$ ...
Jason Xu's user avatar
  • 547
0 votes
1 answer
46 views

Karatsuba multiplication algorithm complexity

Can someone please explain what each of the operations listed refer to explicitly? For instance, how are there "4 additions of 2k-bit numbers"? From inspecting that last expression, I only ...
Jason Xu's user avatar
  • 547
0 votes
0 answers
14 views

Time hierarchy theorem to show $Time(n^7)$ strictly contained in P

I'm relatively new to computational complexity and am trying to use the time hierarchy theorem to show that $Time(n^7)$ is strictly contained in P. I understand that the time hierarchy theorem says ...
Lucas's user avatar
  • 1
2 votes
1 answer
77 views

Complexity of solving systems of linear inequalities with two variables per inequality with additional constraints

Consider a system $X$ of linear inequalities containing at most two variables. In the general case, finding a solution over $\mathbb{R}\cap[0,1]$ can be done deterministically in polynomial time due ...
Daniil Kozhemiachenko's user avatar
0 votes
1 answer
57 views

Computing ${\rm Tr}(ABAB)$ with $B$ diagonal

I want to compute ${\rm Tr}(ABAB)$ where $A$ and $B$ are both symmetric, and $B$ is diagonal. Is there a "simple" way to do this? For example, I know that when $B$ is diagonal, ${\rm Tr}(AB) ...
WazyMaze's user avatar
1 vote
1 answer
60 views

Which grows faster?

I'm looking for some easy way to compare growth rate. I would like to avoid counting the limits of the function. I heard about a way to compare power's of $n^{a}(\log n)^{b}$ but i don't know when ...
piotreczek1's user avatar
2 votes
1 answer
81 views

From a box of balls with 20 distinct colors, after drawing n balls with replacement, what is the probability of observing exactly x different colors?

So assuming there is equal probability of observing any distinct color in a draw, I drew out a pyramid where every draw creates two new edges from its nodes. This then becomes a recursive problem with ...
Cats's user avatar
  • 29
0 votes
0 answers
64 views

Logical Complexity of Ultrafilters

Good morning, I usually really struggle with logical complexity, when I see a statement it's very difficult for me to understand if it should be $\Delta_0$ or $\Sigma_1$ or something else (in the Lévy ...
alvoi's user avatar
  • 939
2 votes
0 answers
54 views

Good book on (Quantum) Complexity and Computability Theories to start learning the theorem $MIP^* = RE$ as an operator algebraist

I am looking for some greatest references that could help me understand the theorem $MIP^* = RE$ ($MIP*=RE$) step by step. The paper (The Connes Embedding Problem: A guided tour) covers various ...
Kadi Harouna Illia's user avatar
1 vote
1 answer
71 views

What does Fagin's result say about NP $\ne$ co-NP?

I'm no expert in this area, and not trying to solve P vs. NP, just trying to understand a formulation of NP. It seems like Fagin's result 1974 is saying that NP is the class of structures ...
Erin Carmody's user avatar
1 vote
2 answers
37 views

Need help with a problem with algorithmic complexity

Is $n^2 = O(n^3)?$ Is that true? How does one go about proving it. If that's true, one can say that the time complexity of Bubble Sort is $O(n^3)$.
Saka Naka's user avatar
0 votes
0 answers
15 views

Complexity of convex feasiblity problem

Can anyone let me know the complexity of the convex feasibility problem, which has m linear constraints and n quadratic constraints?
Thanh Pham's user avatar
1 vote
1 answer
65 views

What are provers and verifiers in computation theory?

Recently I was studying a computation and complexity theory on my own and I have a problem of grasping formally a concept of a prover and a verifier. I think I understand it on the intuitive level, ...
MI00's user avatar
  • 187
1 vote
0 answers
31 views

Unitary evolution of quantum Turing Machine

I have a problem with understanding the concept of unitary evolution of QTM or to be precise how does the Hilbert space, at which unitary evolution acts, looks like. My problem is related to proper ...
MI00's user avatar
  • 187
0 votes
0 answers
36 views

Variant of a Turing machine

Given a standard Turing Machine with the transition function: δ(q,a)=(p,b,L/R), meaning the machines head reads 'a' then writes 'b' instead of 'a' then moves to state 'p' Given a variant to the ...
mpdxd01's user avatar
2 votes
1 answer
68 views

Multiset Matching

Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
SpringLandMid's user avatar
0 votes
2 answers
56 views

Is there a task, so that any algorithm solving this task can not run better than $\mathcal{O}(n)$?

More generally my question is, whether for any $k$ there is a task (e.g. sorting a list of length $n$), s.t. any algorithm solving this task can not run better than $\mathcal{O}(n^k)$? Any idea/...
Joseph Expo's user avatar
0 votes
0 answers
72 views

How to solve this recurrence $T(n) = 2T(n/2) +O(n\log n)$

Problem: Inspiring by the following post, I wonder how to solve the recurrence $$ T(n) = 2T(n/2) +\mathcal{O}(n\log n).$$ I had just thought about this question already when I saw the above post. I ...
Tung Nguyen's user avatar
  • 1,248
0 votes
1 answer
64 views

A precise statement of: "The boolean satisfiability problem (SAT) is in NP"

If $f$ is a function $\mathbb N\to\{\text{True},\text{False}\}$, then I know what it means to say that $f$ is in NP. But if $f$ is a function $A\to \{\text{True},\text{False}\}$, where $A$ is a set, ...
zxcv's user avatar
  • 1,425
0 votes
0 answers
9 views

Number of elementary binary operations (EBO's) required for Long multiplication in binary

How do they get the total of $≤2kl$ EBOs? Shouldn't it require $kl+k(l-1)=2kl-k$ EBOs? And where does the upper bounding "$≤$" come from?
Holland Davis's user avatar
0 votes
0 answers
30 views

The number of bits of a product of two decimal numbers

Theorem. Let us have two numbers $m,n\in\mathbb Z^+$ with $k$ and $l$ bits respectively where $k≥l$. Then $m\cdot n$ has either $k+l-1$ or $k+l$ bits. Proof. Trivially follows from exponent rules. $$2^...
Holland Davis's user avatar

1
2 3 4 5
69