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)

1
vote
0answers
49 views

Complexity of recurrence equation 6

$B(n)=B(⌈ n/\log_2 n⌉)+\theta(n)$ B(2)=1 Here is my attempt: \begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \...
0
votes
3answers
28 views

Complexity analysis of a polynomial and a logarithmic exponential function

I need to find the asymptotic relationship between the functions $f(n) = n^{100}$ and $g(n) = (log_2n)^{(1/2) \cdot log_2n}$. I did the following to show that $f(n) = O(g(n))$: $n^{100} \leq (...
0
votes
1answer
77 views

Is cracking MD5 hash a form of P VS NP problem? [closed]

I have a question,Is cracking MD5 hash a form of P VS NP problem?
1
vote
1answer
34 views

Understanding of what it means to say that a question is in NP

Let's say the the function $f$ can be evaluated in polytime in the size of the input $x$. Are the following problems in NP? Is there an $x$ such that $f(x) = y$ for a particular value of $y$? Find ...
4
votes
0answers
77 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
1answer
20 views

Using Newton Binomials and Combinatorics to reach this big O result?

I'm trying to understand this theorem proof: Theorem. Given a set of n agents, the dynamic programming algorithm, DP, computes an optimal coalition structure in $O(3^n)$ time. Proof of theorem How ...
1
vote
1answer
31 views

What is computational complexity of $Ax=b$ when size of A increasing

I have a linear equation $$Ax=b$$ where $A$ is non-singular matrix $N \times N$, $x,b$ are vector $N\times 1$, $A,b$ are given and I want to find $x$ It is clear that $x$ can find by $x=A^{-1}b$. ...
0
votes
0answers
15 views

Finding All Combinations of a Hierarchical list Where Conditions Are Involved

I want to find all possible combinations of a list that looks like this. a) Option 1 Sub Option 1 b) Option 2 Sub Option 2 c) Option 3 The catch is that there are some simple and some ...
0
votes
0answers
53 views

Average time complexity on finding all common substring of a string

Background Information & Research I'm working on an algorithm where you have to find all common substrings for a given string. For instance find("ABC", "ABCD") would result in {A, AB, ABC, B, BC, ...
2
votes
1answer
107 views

Euclid's algorithm and Gaussian elimination: most computationally efficient approach

I think this is more a mathematics question than a computer science one - but as it is about computational complexity it could be either, so apologies if you think it is in the wrong place... The ...
1
vote
1answer
56 views

On a subset sum version.

In subset sum we ask 'Given $n$ numbers in $\Bbb Z$, is there a subset of them that sums to $0$?' this is $NP$ complete. Consider variant: 'Given $n$ of degree at most $d$ polynomials in $\Bbb Z[x]$ ...
0
votes
1answer
108 views

Algorithmic time complexity of Newton's method vs bisection method

In the context of root finding, it is often stated that the bisection method is slower than Newton's method due to linear convergence. However, I am trying to understand why this is the case from an ...
2
votes
0answers
33 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
2
votes
2answers
60 views

Test symmetricity for a sparse matrix

I have a sparse matrix in LIL (List of Lists) format. I want to test whether the matrix is symmetric or not. Let's say I have n non-default elements. What's the ...
3
votes
0answers
27 views

Complexity Of Recognising Complete Multipartite Graphs

Short question: Is there a linear time algorithm for recognising complete multipartite graphs?
0
votes
1answer
32 views

Need an example shows why SAT is NP problem

Kindly, I have two questions: (1) Are NP-hard, NP-problem, and NP-Complete are just synonyms of each other? (2) I understand that SAT is NP problem that cannot be solved in polynomial time ...
0
votes
1answer
52 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{...
0
votes
2answers
40 views

Complexity of Discrete Mathematics algorithms

I'm new to decision maths and searching algorithms, but one thing I don't understand is how it's determined what complexity (in big-O notation) an algorithm is? For example, I've seen $O(2^n), O(n+m),...
0
votes
1answer
20 views

Structural Induction with Propositional Variables

I've been stuck on this question and I'm confused as to how to approach it: Let $G$ be a set defined as follows: if $x$ is a propositional variable, then $x \in G$; if $f_1,f_2 \in G$, ...
0
votes
1answer
32 views

does $f(n) = O(g(n))$ implies $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$

if $f(n)$ and $ g(n)$ are monotonically increasing, and $f(n) = O(g(n))$. Does it imply that $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$ Well I had a go at it saying I need to show that $f(n)^{...
0
votes
1answer
53 views

How to prove complexity of algorithms

I have three different algorithms which I want to prove if they are solvable in polynomial/subexponential/exponential time. The algorithms are $f(k) = e^{\sqrt{\log{k}}}$, $f(k) = k^2 + \frac{e^{(k+(\...
0
votes
0answers
14 views

How many degrees of freedom exist in an agglomerative hierarchical clustering?

The computational complexity of generating an agglomerative hierarchical clustering from n vectors is $O(n^2)$ (calculating the pairwise distance matrix) dendrogram example However, the total number ...
0
votes
0answers
16 views

A matrix multiplication problem

Suppose we have been given $2n^2$ vectors $a_1,\dots,a_{n^2}$ and $b_1,\dots,b_{n^2}$ each in $\Bbb Z^{n}$. Form an $n^2\times n^2$ matrix $M$ with $i$th row given by $a_i\otimes b_i$. What ...
8
votes
1answer
161 views

Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ...
0
votes
0answers
11 views

Find largest value of the constants that makes the equality true

$$sin(h^2) = a + O(h^b)$$ Find the largest value of a and b such that the equality holds. I tried to use the truncated Taylor series expansion of $sin(h^2)$, but the derivatives of the function are to ...
0
votes
0answers
21 views

Compare Complexity of Graph (Landau)

Assume I know that there is an algorithm of complexity $ \mathcal{O}( \vert V \vert^2 \vert E \vert ) $ for a Graph $G(E,V)$. How do I compare this for example to the complexity of $ \mathcal{O}( \...
1
vote
0answers
19 views

Does there exist a $k$ such that for all $n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$?

Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$? I ...
0
votes
2answers
29 views

Bubble sort complexity calculation, unsure how it went from one step to another.

I'm looking at my textbooks steps for calculating the complexity of bubble sort...and it jumps a step where I don't know what exactly they did. I see everything up to that point using summation ...
2
votes
1answer
70 views

Math Contests: How to Solve Equation with $x$ in the Denominator

Okay, I realize this seems like a really stupid question, but on a math contest (without calculators) I got down to this equation: $$\frac{26}{672-x} + \frac{24}{372-x} = \frac{50}{480-x}$$ ...
0
votes
1answer
20 views

Prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$

I'm asked to prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$ I know that for Big O, I need to show: $f(n) <= c*g(n)$ But I'm not sure how to show this, since it involves theta. Any help would ...
1
vote
1answer
66 views

How long does the General Number Field Sieve actually take?

According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer. Using the complexity equation for the General Number Field Sieve with <...
1
vote
1answer
52 views

First-order logic: largest size among smallest finite models for formulas of a given length

Apologies for the somewhat cryptic title. For any first-order formula X, let ssm(X) be the size of the smallest finite model of X. By size I mean number of individuals. So, for example, ssm('Fa &...
2
votes
1answer
16 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
2
votes
0answers
39 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
0
votes
0answers
27 views

What is an example of a search problem that is not in NP?

I feel like there should be an easy example, but I can't think of one. So, specifically, I am looking for a Yes/No search problem that is not in the class NP. When you learn about P and NP, you get a ...
1
vote
1answer
25 views

How to solve this recurrence $t(n) = ( 2^n )( t(n/2) )^2$ with $t(1)=1$?

I have been wondering about how to solve this recurrence but I don't get to any feasible solution. How can I do it?
0
votes
1answer
40 views

Find a function $f(n)$ such that neither $f(n) = O(log n)$ nor $f(n) = \Omega(n)$ holds.

Any hints on this problem? I want to find a function $f(n)$ which is: NOT $f(n) = O(log n)$ NOT $f(n) = \Omega(n)$ So it must hold that: $c_1 * log n < f(n) < c_2 * n$ and $c_1, c_2$ are ...
0
votes
2answers
90 views

An inequality on an arbitrary function

I'm trying to find the complexity of a program and reduced the question to the following one: Let $g$ be a function from natural numbers (including $0$) to natural numbers. Assume that for every $n \...
1
vote
1answer
28 views

How to show the running time of the following algorithm? [closed]

The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe ...
0
votes
0answers
10 views

What is the complexity of the arithmetic operations in base $b$?

Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there ...
0
votes
1answer
31 views

There is no algorithm which has a runtime of $O(n^2)$ and $\Theta(n^\frac{7}{2})$

How can I proof that there exists no algorithm which has a runtime of $O(n^2)$ and $\theta(n^{\frac{7}{2}})$? Or is this possible because logically I would say that if a function is $O(n^{\frac{7}{2}...
0
votes
0answers
6 views

A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$...
1
vote
2answers
28 views

Time Complexity Calculation

I'm currently working a few exam question, and got stuck at this point. I am given that a Quicksort algorithm has a time complexity of $O(nlog(n))$. For a particular input size, the time to sort the ...
1
vote
0answers
47 views

How can I plot the complex function in 2D?

My function: $$sin(wt-jT) \tag{1}$$ where $j$ - complex unit, $T=0.1,\ w=8 \pi,\ t=[0,0.01,0.02..100]$ I transform it to function with real arguments: $$\sin(wt)\cosh(T)+j\cos(wt)\sinh(T) \tag{2}$$...
0
votes
1answer
25 views

Help solve a computational complexity problem

Find the tight computational time ($\Theta$ notation) complexity of the following function Of course an exact solution is $\sum\limits_{i = 1}^{3{n^3}} {\frac{{2{n^3}}}{i}} $, but I am not able to ...
1
vote
0answers
18 views

Applying the convolution theorem in the presence of a twiddle factor

The convolution theorem says that a 2-d cyclic convolution like $C = U \ast V$ can be evaluated more quickly than doing the raw sum $C_{i,j} = \sum_{a,b}^n U_{a,b} V_{i-a,j-b}$ for each point (assume ...
1
vote
0answers
13 views

A polynomial majority function

Let us introduce a boolean function $F(x_1,x_2,x_3,...,x_n)$, where $F=1$ when most of the variables $x_1,x_2,...,x_n$ are equal to $1$ and $F=0$ otherwise. This is called a majority function. The ...
1
vote
1answer
39 views

Smart way to calculate floor(log(x))?

I thought of an algorithm that involves $\lfloor \log_{b} x \rfloor$ and am trying to determine its computational complexity. At first glance my algorithm looks polynomial, but I read that my ...
2
votes
1answer
59 views

If someone finds a polynomial time algorithm for a problem in NP, will we be able to construct polynomial time algorithms for all problems in NP?

The existence of a polynomial time algorithm for a single problem in NP implies the existence of polynomial time algorithms for all problems in NP (correct me if I'm misunderstanding this). Suppose ...
1
vote
0answers
33 views

How to resolve this computability paradox?

Let's define two Turing machines, $T_1$ and $T_2$, as follows: Given a number $n$ as input, let $T_1$ be a Turing machine that enumerates over all pairs $(p,s)$ where $p$ is the code of some Turing ...