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
24 views

What is computational complexity of a coding technique

In my previous Question Help in understanding a coding technique based on inverse mapping of a dynamical system I learnt how to apply chaotic map in coding theory in communications. Steps: (1) The ...
0
votes
0answers
17 views

Time complexity analysis of partitioning method

http://www.stat.cmu.edu/~cshalizi/462/lectures/05/05.pdf tutorial explains about how a generating partition can produce 0/1 symbols from a dynamical system. The technique is called Symbolic Dynamics. ...
0
votes
0answers
7 views

Complexity of Munkres Algorithm

At the moment I'm trying to derive the complexity of the Munkres algorithm in the worst case. For this I'm working with this website and currently I have following complexities for the steps: ...
0
votes
0answers
14 views

Computational complexity of conjugate gradient method for a positive-semi definite Hermitian matrix

Let us assume that we want to solve the linear system: $\mathbf{A}\mathbf{x} = \mathbf{b}$ with the conjugate gradient method. $\mathbf{A}$ is a positive semi-definite Hermitian matrix. The ...
0
votes
1answer
14 views

Asymptotic notation basics

Say that we have the function $$ f(n)=kn, \, k>0 $$ does that imply the following? $$f(n) \in O(n), \, f(n) \in \Theta(n) \text{ and } f(n) \in \Omega(n)$$ I'm fairly new to these notations and am ...
0
votes
0answers
7 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
-2
votes
0answers
21 views

What is phase transition in 3-SAT [closed]

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
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
14 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 ...
1
vote
1answer
44 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
22 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 ...
1
vote
0answers
38 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
23 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) < ...
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 ...
0
votes
1answer
56 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 ...
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 ...
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)$?
-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 ...
2
votes
0answers
24 views

One way functions and P = NP?

How can I show that no one way functions exist under assumption of P = NP?
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 ...
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 ...
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. ...
7
votes
1answer
103 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$ ...
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

Time complexity for inner loop

What's the time complexity for this code? ...
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
271 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
32 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
32 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 ...
1
vote
1answer
67 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
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?
5
votes
1answer
121 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 ...
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
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
1answer
21 views

complexity of $\ {n \choose n/3}$

I know that the complexity of this combination $\ {n \choose n/3}$ is of $\theta(n^{n/3})$ , but I'm in need of help proving it.
0
votes
0answers
23 views

Help me to find mixed chinese postman problem (MCPP) complexity

I know that MCPP is NP-Complete. Also, I have problem formulation: Chinese postman problem for mixed graphs. I was given a task to evaluate the number of operations required for a complete re-election ...
0
votes
1answer
34 views

Big O for factorials

Hello I have trouble proving:$$(n+1)!\notin O(n!)$$ My first step is the following: $$(n+1)!-cn!\le0$$ Can you please help me with the next step?
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 ...
2
votes
2answers
21 views

What does $\mathbb{Z}[X]$ for a polynom mean?

I have a proof saying that a Polynom $p \in \mathbb{Z}[X_1,...,X_m]$ I'm a bit confused of this notation because neither X nor the m is explains somewhere. Does somebody of you know the notation?
0
votes
0answers
11 views

Time taken to run a function R(n,a)

R(n, a){ if n = 1 return(a); if n > 1 return (R(n − 1) + R(n − 1) + 1); } Could you please explain me why the estimated time taken to run R(n, a) as a function of n is: (2^(n−1))*(a + 1) − 1 ? ...
0
votes
0answers
23 views

How can I solve this Big O exercise?

How can I prove that n log2(n) ∈ O(log(n!)) is true? We start by supposing that f(n)< c* g(n) is true, which means that n log2(n) > c*log(n!) for all n>n0 and c>0.
0
votes
2answers
47 views

What is the Order (Big O) of this polynomial?

$$\frac{2n^{14} + 7 n^8 - 3}{3n^8 - n^4 + 3}$$ If this division is $p(n)$, I have to write $p(n) = O(n^k)$ I guess the answer is $n^6$, but how can i solve it step by step?
0
votes
0answers
30 views

Turing Machine problem for unary division

How do I design a turing machine for this? Divide a given number by two in the unary number system.The quotient and the remainder should be written on the tape separated by a blank.