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)

5
votes
2answers
69 views

At what point does exponential growth dominate polynomial growth?

It's well-known that exponential growth eventually overtakes polynomial growth (link, link). So for any non-negative integer $d$ and positive $\epsilon$, there exists $t^* \ge 0$ for which $$ 1 + ...
0
votes
0answers
25 views

Looking for info on representation of a diophantine equation as system of equations over finite field/boolean algebra

Suppose that $x$ is a positive integer. Fix some prime $p$. Then there exists some non-negative integer, $L$, and $\{x_0, x_1, . . . , x_L\} \subseteq \{0,1,...,p-1\}$ such that, $$x = \sum_{n=0}^{L}...
1
vote
1answer
40 views

MATLAB “back slash” computation [closed]

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below: Note: all of these are for m = 5000 1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; ...
2
votes
2answers
40 views

How many arithematic operations(flops) are to $n×(n+1)$ matrix of system?

Source: Linear Algebra and Its Applications David C. Lay A system of n equations in n unknows correspond to $n×(n+1)$ augmented matrix. One book says the reduction(elimination) to echelon form can ...
0
votes
0answers
17 views

Hardness of approximation for linear equations

Given a system of linear equations in n variables with coeffcients that are rational numbers, determine the largest subset of equations that are simultaneously satisable. Show that there is a ...
2
votes
0answers
43 views

Fast algorithm to recognize sortable sequences

Every sequence is sortable in the worst-case by a $O(n^2)$. However, if we restrict sorting primitive, we get an interesting problem. I am interested in this sorting problem: Input: a sequence $A$ of ...
1
vote
0answers
52 views

Good books on Algorithms for a math major without any programming experience?

I couldn't find this question anywhere else so it may not be apt. I am an undergraduate mathematics major and during my discrete math class I really enjoyed the study of algorithms and recursive ...
0
votes
4answers
41 views

Prove that an upper bound is incorrect

Probably a simple question that I cant figure out from data structure course: I need to disprove the following statement: $$ 8n^3 + 12n + 3\log^3n \ge n^4 $$ Now I know that from some value $n_0\in\...
0
votes
0answers
16 views

(Complexity) Subset of set of premises and the entailment problem

I've a finite set of propositional formulas $\Gamma$ and a logical conclusion $\psi$ over variables $X$. The following decision problem arises: Does a cosistent subset $\Gamma' \subseteq \Gamma$ exist ...
0
votes
0answers
21 views

Determine number of vertex in a graph

I'm trying to determine the number of vertex in a graph $G=(V,H)$ where: $\displaystyle V = \left\{ v = (x_1, x_2, x_3) \in \mathbb{Z}_p^3:\sum_{i=1}^3x_i\equiv0\right\}$ with $p \ge 3$. Equivalent ...
0
votes
0answers
12 views

Does ray tracing have any speed ups in algorithm running time in the frequency domain?

Could ray tracing be Fourier-transformed so that all calculations are done in the frequency domain? I think ray-tracing a set of rays $S$ from the eye into the view frustum might be more efficient ...
10
votes
3answers
208 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
1
vote
1answer
20 views

Find a function f(n) such that T(n) is $\Theta(n \cdot log(n)) $

Find a function f(n) such that $ T(n)=16 \cdot T(\frac{n}{4}) + f(n) = \Theta(n \cdot log(n)) $ Also, another section of the question is where $T(n) = \Theta(n^{2})$ I've tried using the master ...
0
votes
0answers
22 views

Parallel Computing Mathematical Question (Amdahl's Law)

I have the following question, and I'm not even sure how to start this: A serial program takes T (e.g. ) hours to complete its execution. Assuming that the interprocess communication in a parallel ...
3
votes
0answers
50 views

Is it faster to calculate inverses of symmetric matrices as opposed to asymmetric matrices? How?

I know there are several methods to inverse or decompose matrices. I am looking for a comparison of the computational cost of inverting an arbitrary real, symmetric matrix vs a real, asymmetric one. ...
0
votes
1answer
14 views

Computational Complexity for lower triangular matrices

I am trying to find the complexity $$ l_{ij} = \frac{1}{l_{jj}} \left(a_{ij} - \sum l_{jk} l_{ik} \right). $$ I have considered $a_{ij} - \sum \ldots$ as being one operation, $l_{jk} \times l_{ij}$ ...
1
vote
0answers
55 views

Complexity of FFT algorithms (Cooley-Tukey, Bluestein, Prime-factor)

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm. Unfortunatelly, I'm a little lost in the process. ...
11
votes
3answers
143 views

How does one interpret statements like: “The traveling salesman problem is NP-complete?”

The world abounds with statements like: The traveling salesman problem is NP-complete. But when I follow try to follow the Internet's links "down the rabbit hole," I don't get a truly sensible ...
2
votes
0answers
76 views

Relationship between Complexity and Computability

As a response to comments,i'd like to put it in an abstract way,hoping this will make things clearer: f is a well-defined function of countably many inputs:f(a1,...,an,...). For a set of n objects {a1,...
2
votes
0answers
54 views

Undecidable problems involving elementary functions

I am reading the article "Some undecidable problems involving elementary functions of a real variable" by Daniel Richardson and have some problems with understanding Lemma Three : Let $h(w)=w\sin w, ...
0
votes
0answers
36 views

Prove that for every function $s:\mathbb N\to \mathbb N$ with the following constraints holds that:

Hello guys I'm studying Computational Complexity and I have stumbled upon the following question which I has no idea how to even start proving. I would appreciate any help. Prove that for every ...
0
votes
2answers
36 views

Why these algorithms have a linear complexity function?

Considering the following algorithms: ...
0
votes
0answers
44 views

What are the minimum hard constraints that cause the nurse scheduling problem to be NP-complete?

A client wishes to simplify the nurse scheduling problem to 'bypass' the NP-complete nature of this problem. He is hoping to do so by removing the requirement that there are any constraints for any ...
0
votes
1answer
40 views

When is $(mn+1)/(n-m)$ an integer?

For an integer $n$ I would like to find all integers $m$ with $n/2<m<n$ and $$ \frac{mn+1}{n-m} $$ an integer, that is, $$ mn\equiv-1\pmod{n-m}. $$ How can I find these $m$? I could just check ...
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
31 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
78 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
16 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
58 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
114 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
124 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
34 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
63 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
54 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
18 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
163 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
22 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}( \...