Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

0
votes
0answers
7 views

Classify $\{ \langle M \rangle |M \text{ is a turing machine so } L(M) \leq_M A_{TM} \}$

Let $$L = \{ \langle M \rangle |M \text{ is a turing machine so } L(M) \leq_M A_{TM} \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} ...
6
votes
0answers
82 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
2
votes
1answer
13 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
0
votes
1answer
60 views

What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$ \forall X : A^X \subseteq B^X $$ is proven, disproven, or unknown. What does this ...
0
votes
0answers
18 views

How to solve master theorem $T(n) = 3T(n/2) + (n^2)/log n$

Im trying to solve this master theorem $T(n) = 3T(n/2) + n^2/log n$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = n^2/logn$. Which rule to apply now and how to solve this?
-2
votes
0answers
21 views

What is phase transition in 3-SAT [on hold]

I understand the basic concept of 3SAT. Can anyone explain about what is phase transition in 3-SAT? As simple as possible. I tried google but the result come out which is far from what I understand ...
0
votes
0answers
136 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computability theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
0answers
10 views

Determine an algorithm for $LU$ factorization and determine the number of operations [duplicate]

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of ...
0
votes
0answers
7 views

Determine an efficient algorithm and describe the computational/storage complexity

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
0
votes
1answer
13 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
0
votes
1answer
43 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
1
vote
0answers
21 views

Matrix vector product $O(n)$

Consider the matrix vector product $x = Lb$ where $L$ is an $n\times n$ unit lower triangular matrix with all of its nonzero elements equal to $1$. For example if $n = 4$ then \begin{align*} x ...
-2
votes
0answers
25 views

Trouble with Strassen's algorithm [closed]

I just recently started learning about matrix multiplication. I' teaching myself through the internet mostly and I can't quite grasp the concept of Strassen's algorithm. I understand the 2x2 matrix ...
1
vote
0answers
37 views

Running time of Edmonds-Karp algorithm

I have to prove that the running time of the Edmond-Karp-Algorithm is $\Theta({m^2}n$) by providing a family of graphs, where the Edmond-Karp-Algorithm has a running time of $\Omega({m^2}n$). I have ...
0
votes
0answers
9 views

Computational/Storage compexity in solving a linear system

Suppose we have $$y = L_i x$$ where $x\in\mathbb{R}^n$ and $y\in\mathbb{R}^n$ and $L_i$ is a elementary unit lower triangular system which can be represented by $$L_i = x + l_i e_i^{T}$$ Determine an ...
2
votes
1answer
21 views

Busy Beaver unprovoable for large inputs?

From Wikipedia on the busy beaver, there is a true-but-unprovable sentence of the form "$Σ(10↑↑10) = n$", and there are infinitely many true-but-unprovable sentences of the form "$Σ(10↑↑10) < ...
-4
votes
0answers
18 views

What is the big O notation of the program in the following paper? [closed]

Please tell me the big O notation of the program in the following paper, I think is n^5.
0
votes
0answers
34 views

Is there a mathematical way to quantify the complexity of an equation that relates variables to each other?

Is there a mathematical way to quantify the complexity of an equation that relates variables to each other? Some examples of equation that interest me are, for example basic equations with a lot of ...
0
votes
1answer
55 views

How quickly can this function be computed?

I can show that $\lambda (n)=i^{\tau(n^{2})-1}$, where $\lambda (n)$ is the Liouville function, $\tau(n)$ is the divisor function, and $i$ is the imaginary unit. My question is as stated, and what is ...
2
votes
0answers
24 views

Algorithmic complexity of testing whether a permutation belongs to a subgroup generated by a set of permutations

Let $S=\{S_1,S_2,S_3,\ldots,S_m\}$ be a set of permutations on $n$ symbols (in other words $S$ is a subset of a symmetric group on $n$ symbols) and $P$ be a permutation on $n$ symbols. What is the ...
1
vote
1answer
22 views

Describe a polynomial-time algorithm to compute the function expressed by the boolean formula

Let $\varphi$ be a boolean formula of $n$ variables and $(t_1, t_2,\ldots,t_n) \in \{0, 1\}$ be an assignment. How to describe a polynomial-time algorithm to compute $\varphi(t_1,t_2,\dots, t_n)$?
1
vote
0answers
16 views

Is there any example of real-life decidable problem that is not in EXP?

In order to illustrate an introduction on computational complexity, I am trying to find examples of real-life problems for every one of the main complexity classes: $P$, $NP$, $EXP$, $R$ and ...
0
votes
1answer
437 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
8
votes
4answers
170 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...
4
votes
1answer
104 views

Cryptosystem safer than RSA

As you know, the RSA system is based on the fact that factoring a number $n$ cannot be done in polynomial time ($P(\ln(n))$, not $P(n)$). The factoring problem is known to be in $NP$, but we don't ...
-5
votes
1answer
84 views

Is this proof of P and NP correct? [closed]

I was searching and found this interesting proof in the folowing Scribd page https://pt.scribd.com/doc/307232804/Solving-the-Traveling-Salesman-Problem-and-establishing-P-NP
0
votes
0answers
8 views

Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

How would you quantify the computational complexity of feasibility LPs? Say for example an LP with $m$ inequalities : $$ \begin{cases} \mathbf{a_i}.\mathbf{x} \leq b_i, i \in [m] \\ \mathbf{x} \in ...
1
vote
1answer
431 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = ...
2
votes
0answers
22 views

One way functions and P = NP?

How can I show that no one way functions exist under assumption of P = NP?
1
vote
3answers
123 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
0
votes
1answer
40 views

Proving that $\log x$ is Big Oh of $x^k$ for every positive k

Can I know a way to prove the above condition purely by the definition (and may be Taylor Series) and without using L'Hospital's rule? It is obvious for k greater than or equal to 1 but how can you ...
4
votes
0answers
76 views

The role of the extraction matrix in a Kalman filter

The extraction matrix shown as $H_k$ below, transforms the state vector into a form that can be subtracted from the measurements vector: $\hat{X}_k = \hat{X}_k^- + K_k ({z}_k - H_k \hat{X}_k^-)$ ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
0
votes
1answer
14 views

Time complexity for loop with pow and log n advancement.

So, I'm analyzing this loop. And I'm not sure of the time complexity. ...
1
vote
3answers
43 views

What is the value of $x$ when $a^\frac{1}{x}=1$?

I used to compute complexity of an algorithm which reaches to constant value after x level because of $a^\frac{1}{x}=1$. Now I need to find $x$ to reach answer. To describe more : my recursive ...
0
votes
1answer
30 views
1
vote
0answers
17 views

How can we make Cook-Levin Reduction an implicit log space reduction

This is an exercise mentioned in lots of places. I have searched around for detailed answers, but none of them has explained clearly on a critical part of analysis. Setting: we have an oblivious ...
12
votes
1answer
270 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
0
votes
0answers
31 views

If graph isomorphism yields a polynomial time algorihtm.

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
2
votes
1answer
31 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...
1
vote
1answer
31 views

Hamiltonian path problem vs other NPC problems

If we can solve the Hamiltonian path in time $O(n^4)$ then you can solve any other NPC problem in $O(n^4)$ time. Is it true of false? I think it is false, even tho Hamiltonian path problem in NPC it ...
0
votes
1answer
415 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
0
votes
2answers
55 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - ...
1
vote
1answer
63 views

Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
0
votes
0answers
7 views

Algorithmic complexity from knowing complexity due to two different factors.

I have an algorithm that has complexity depending on two factors $n$ and $m$. If I know that fixing $m$ I have complexity $\mathcal{O}(n^p)$ and fixing $n$ I have complexity $\mathcal{O}(m^q)$, can I ...
1
vote
1answer
77 views

Computational complexity of solving linear diophantine equations?

Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$? I found some estimate on computing the Smith Normal Form $N$ such that ...
5
votes
1answer
120 views

Solving the Gobblet game

In 1995 the Connect-4 Game was solved with a brute force approach. Using the standard 6 high / 7 wide grid, first player can force a win in 41 moves. Complexity of the Connect-4 game could be ...
1
vote
1answer
443 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
0
votes
1answer
25 views

What will happen if any language in NP ∩ co-NP will become NP-complete?

I approached this question like this: Let B ∈ NP ∩ co-NP and B is also NP-complete. Then any other problem in NP can be reduced to B. Now take A ∈ co-NP. Then ~A ∈ NP which can be reduced in ...
1
vote
1answer
24 views

Omitting the refference to a particular logarithmic base - order notation

How can I prove by using the Order notation definition that we can conventionally refer to an algorithm taking "log time", without referring to a particular logarithmic base?