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

Formula for running-time complexity

I'm regarding a stochastic process $(X_t)$of which the mean starts at $O(n)$ and is reduced by the factor $(1-r)$ in each step with $r = \Omega (1/n^9)$, so $$E(X_{t+1}) \leq E(X_t) (1-r) .$$ Now it ...
0
votes
1answer
16 views

How can you test if a function is bounded by another?

I am trying to learn about complexity theory, which states that $f(n)$ is in $O(g)$ if, for some $C > 0$, $f(n) \leq C\cdot g(n)$ for all $n \in \mathbb{N}$. That's well and good; it makes sense to ...
1
vote
1answer
23 views

How is this example big-omega?

I'm having a bit of difficulty understanding big-omega and big-theta of this particular function which is supposedly Ω(16n + 33) $5n − 2 = Ω(16n + 33)$ I understand that the there is some constant c ...
1
vote
0answers
11 views

How to obtain the minimizer parameter $\lambda$ for this computational complexity?

I'm trying to read a certain text, where they reach a computational complexity depending on scalars $a,b,c$ and a parameter $\lambda >0$ $$ O\left(\left\lceil\sqrt{\lambda a + \lambda^2 b^2} ...
12
votes
3answers
661 views

Must an algorithm that decides a problem in NP also produce a solution?

I think I have a basic misunderstanding in the definition of a decision problem. It's widely believed that a proof of P=NP would break all modern cryptography, for example:- ...
12
votes
3answers
308 views

Efficient computation of $E\left[\left(1+X_1+\cdots+X_n\right)^{-1}\right]$ with $(X_i)$ independent Bernoulli with varying parameter

Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ ...
3
votes
1answer
68 views

What makes the permanent lot more difficult than the determinant

The permanent of an $n$-by-$n$ matrix $A$ = $(a_{i,j})$ is defined as: $\operatorname{perm}(A)=\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^n a_{i,\sigma(i)}$. ...
1
vote
0answers
22 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
0
votes
0answers
19 views

How to efficiently select a subset of elements that maximizes a certain property? (entropy)

I need to select $k$ elements from a pool containing a much larger number $N$ of elements. The selection must be done in a way that a function $h(\{z_{i_1},\ldots,z_{i_k}\})$ is maximized or ...
-4
votes
0answers
27 views

set of points of orthogonal vectors [closed]

To every point M of affix Z we associate the point P of affix Z-1 and the point Q of affix z. Determine the set of points of M such that PM is orthogonal to pQ .
0
votes
0answers
44 views

Computational complexity of the following quadratic program (QP)

Let $A^TA$ be a $n \times n$ matrix. I have the following quadratic program to solve: \begin{array}{rl} \min \limits_{x} & x^T A^T A x \\ \mbox{subject to} & \sum_{i=1}^{r} x_i =1, ...
0
votes
0answers
14 views

Reduction to Halting problem

I have the following problem. Prove by reduction to the halting problem, that $L:=\left \{ <M> | L(M)=\emptyset \right \}$ is undecidable. L(M) is the defined as: $L(M) = \left \{ w \:| M ...
0
votes
0answers
18 views

What is the best time complexity for this case?

I only want to know if the following system has any integer solution or not. Actually, I do not need to know the solution(s), and only need to know the answer of question "Does the system have any ...
0
votes
0answers
21 views

Compute asymptotic expansion of an integral along the unit circle

I want to compute the asymptotic expansion of the following integral with $t\rightarrow +\infty$ $\int_C\dfrac{(1+u)^{t+4}}{u^5}du$ where $C$ is the unit circle. I really appreciate your help. By ...
2
votes
1answer
31 views

What is the best time complexity of checking the inequality $a_1x_1 + \cdots + a_mx_m \le K$ to have a non-negative integer solution?

We know that all the coefficients $a_1, a_2, \ldots , a_m$ are integer. Also, $K$ is an integer number. I only need to know if the inequality has a integer solution or not. It means that there is no ...
2
votes
1answer
134 views

the algorithm and computation cost for truncated SVD in rank k

It seems that the time cost of truncated SVD in rank k for matrix $A\in R^{m\times m}$ is $O(m^2 k)$. Could anyone show me some algorithms to calculate truncated SVD with the above time complexity?
0
votes
1answer
28 views

Seeking the Recommendation on Complexity Theory books

S.E advisers, I am a rising college junior in US with a major in mathematics and an aspiring applied mathematician in the fields of theoretical computing. I just recently got a research project on ...
3
votes
3answers
796 views

How to calculate a Modulo?

I really can't get my head around this "modulo" thing. Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5. Also, what does this ...
2
votes
0answers
50 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
0
votes
0answers
14 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
0
votes
2answers
22 views

Max 2-sat and clause size

I've seen that Max 2-Sat is NP-complete, are there instances in which every clause has exactly $2$ variables which are $NP$-complete? Or do all such instance need to contain a clause of exactly 1 ...
0
votes
1answer
40 views

Time complexity of a simple factoring algorithm?

This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides ...
0
votes
0answers
49 views

Why finding chromatic number is NP-Hard?

We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color . But why the coloring is ...
2
votes
1answer
50 views

Doubt about claim about complexity of edge coloring powers of the line graph

Likely I am misunderstanding/missing something, but a claim in a paper appears wrong to me. According to Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation p. 2 Unless ...
2
votes
1answer
28 views

Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?

Suppose a hypothetical decision procedure $A$ could solve NP-complete problems in polynomial time (of course implying $NP = P$). Many NP-complete problems take the form of constraint satisfaction, ...
2
votes
1answer
81 views

Why doesn't the decision problem for Presburger arithmetic demonstrate that $\mathsf{P} \neq \mathsf{NP}$

From Wikipedia's article on Presburger arithmetic: Then Fischer and Rabin (1974) proved that any decision algorithm for Presburger arithmetic has a worst-case runtime of at least $2^{2^{cn}}$, ...
2
votes
1answer
16 views

Show that $\log^{i} n \in O(n^{j})$ for $i,j > 0 $

I want to show that $$\log^{i} n \in O(n^{j})$$ I tried to apply L'Hospital and came up with the following: $$\lim\limits_{n \rightarrow \infty}{\frac{\log^{i} n}{n^{j}}} =$$ $$\lim\limits_{n ...
0
votes
1answer
309 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 ...
0
votes
0answers
15 views

Time Complexity of algorithm

Suppose I have an output of roughly $n^k k \log_{10} n$ digits where $A$ has $n$ elements and we have to list $n^k$ tuples with $k$ components each. What would be the time complexity class of such a ...
0
votes
1answer
21 views

$O(\text{polylog}(1/\epsilon))$-time Algorithm for Numerical Integration to Within Additive $\epsilon$?

I'm trying to approximate a 1D definite integral to within an additive $\epsilon$ for a given $\epsilon$. I was wondering whether there is an $O(\text{polylog}(1/\epsilon))$-time algorithm for this. ...
2
votes
1answer
28 views

Are there slight modifications to NP-complete problems which reduce them to P?

Recently I revisited the infinite harmonic series and its barely diverging sum, and how removing all the composite numbers from the sum still produces a divergent series (even more barely). In ...
8
votes
1answer
1k views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
0
votes
2answers
126 views

Computation complexity with simple algebra expression reduction

I'm watching this computer science video on computational time complexity of a function where they introduce some maths and it doesn't make sense to me. I'm not even sure what the name for this maths ...
0
votes
1answer
21 views

The time complexity of the n-ary cartesian product over n sets

Recall that the Cartesian product $A\times A$ is defined as the set $\lbrace (x,y):x\in A ,y \in A \rbrace$ . Thus, if for example, $A=\lbrace 1,2,3 \rbrace$,$A \times ...
0
votes
0answers
35 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
0
votes
1answer
24 views

How many coins do we need to get $k$ amount

In the far away land of coinsville, they use $4$ different coins as currency, $\{1,10,100,200\}$ What is the computational class of the amount of coins (minimal!!) we need to get $k$ amount? Well, ...
4
votes
1answer
105 views

What background is needed to study quantum game theory?

Currently I am learning ( a beginner ) about Bell inequalities and device independent outlook on quantum mechanics. I come across some papers using these concept in quantum game theory. Most of the ...
0
votes
1answer
11 views

max degree polynomial for time complexity considerations

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some ...
2
votes
1answer
20 views

Problem with my simple algorithm to count repetitions

We have two arrays $A,B$ with sizes $n,m$ respectively. We know that $m \geq n$. We also know that no array contains the same number twice. Propose an algorithm that prints how many numbers appear in ...
0
votes
1answer
67 views

Complexity of $\binom{n}{2}$

So: $$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$ Using Stirling's approximation we have: $$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi ...
1
vote
0answers
20 views

How to properly detect rows to be swapped in a Gaussian elimination?

I'm trying to describe an algorithm for solving solvable linear systems. The Gaussian elimination is pretty straightforward in terms of adding multiples of rows. However, consider the following ...
0
votes
0answers
20 views

Computing the Log-Euclidean distance efficiently by using eigen-analysis.

Let $A,B\in\Bbb{S}_{++}^n$ be two symmetric positive definite $n\times n$ matrices with real entries. The Log-Euclidean distance between these matrices is defined as follows $$ d = \lVert \log(A) - ...
2
votes
3answers
34 views

Prove correctness of simple greedy algorithm to find max

We have $2n$ values $x_1,x_2,x_3,\ldots,x_n$ and $y_1,y_2,y_3,\ldots,y_n$ such that the pair $(x_i,y_i)$ represents the location of a city $i$. Assume there is no straight line that goes through all ...
-1
votes
1answer
66 views

A quicker algorithm.

Consider an algorithm which essentially counts to a certain number then halts. Counting Algorithm C Given any $n \in \Bbb N$ Step 1 $x_0=0$ Step 2 $\text{if} (x_n =n)\ \text{then}(\text{halt}) $ ...
1
vote
2answers
76 views

Is there any sort algorithm quicker than Quicksort given a random array of integers?

How can we proof (mathematically) that any complexity of sorting algorithm that sorts a random array of integers is no better than $O(n\log n)$?
0
votes
1answer
52 views

Is finding generators of finite fields hard?

Task: Given $n$, find a generator of $GF(n)^*$. Is there any evidence this is hard? Maybe a reduction from another problem presumed hard? Finding the orders of elements should be hard because I ...
2
votes
3answers
35 views

A=LU decomposition time complexity

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix. Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
0
votes
1answer
24 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
1
vote
0answers
21 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
2
votes
1answer
41 views

Is there an algorithm to find minimum number of undefinable words in a dictionary?

Here's the problem. Every word in a dictionary is defined by a set of other words. For example "cat" may be defined as "small mammal with fur". Can we choose a set of 'base' or 'prime' words such that ...