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

Bijection between tensors and permutations (in linear $O(n)$ time)

The number of permutations of the set $S=\{1, \dots, n\}$ is $n!$, or in other words the permutation group $S_n$ has $n!$ elements The number of tensor components of a tensor in $n$ dimensions ...
0
votes
1answer
21 views

Calculate difference in throughput between two computers when the time complexity is $2^n$

The time complexity for some algorithm is $T(n) = 2^n$ where n is the size of inputs. A particular computer takes t seconds to process n inputs. How many inputs can a computer that is 64 times as fast ...
2
votes
1answer
52 views

Is $(n!)^n$ complexity just said to be $O(n!)$ complexity?

I know that $n!$ complexity is higher than exponential complexity and big-O notation says always use the highest growing $n$ term for the naming. But, seeing as this is a factorial to the power of $n$ ...
0
votes
0answers
89 views

For each pair of functions f1 and f2 in (a) - (h) below, provide functions h1

For each pair of functions f1 and f2 in (a) - (h) below, provide functions h1 and h2 such that f1 = Θ(h1) and f2 = Θ(h2). The functions h1 and h2 should be in one of the following forms: n k logp n or ...
0
votes
0answers
28 views

The DNF complexity of a function and its complement

If $f:\{0,1\}^n \to \{0,1\}$ is a $DNF$ formula with $t$ terms of width $w$, what can we say about the $DNF$ complexity of $\neg f$ (i.e., what is the number of terms and width needed to represent ...
0
votes
1answer
29 views

Rigorously prove while loop executes $\lceil \log_{2}(\log_{2}(n)) \rceil$ times

Problem Suppose we have the following code k := 2 while k < n do k := k * k end while How many times will the loop execute? Current Work My intuitive ...
1
vote
2answers
72 views

Is this an application of the Birthday problem?

Let's say there is some positive integer n that is somewhere between 0 and N (also a positive integer). I tell the program to start generating random (or pseudo-random) number pairs (modulo N) and ...
0
votes
0answers
47 views

Looking for references on the complexity of computation of a basis transformation matrix

I'm looking for some references on the complexity for the following kind of problem: Given two Basis $(a_1, ... ,a_n)$ and $(b_1, ..., b_n)$ of the $K(x)$-vector space $V$ I want to compute the ...
2
votes
1answer
26 views

Using a linear function as a routine to determine a matrix

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be a linear function, i.e., $$F(\alpha x + \beta y) = \alpha F(x) + \beta F(y)$$ Suppose you are given a routine that returns $F(x)$ given any ...
0
votes
1answer
32 views

01-integer programming

can someone please explain to me what is meant by easily converting negative objective function coefficients? This may seem like a restrictive set of conditions, but many problems are easy to ...
2
votes
1answer
21 views

Prove that $co-RP \subseteq RP^{RP}$

This appears in solutions to an exercise I had: Question: Prove that $RP^{RP}=RP$, or show that it is equivalent to an open question. Answer: $RP^{RP}=RP$ is equivalent to the open question ...
3
votes
0answers
63 views

Asymptotic running time for multiplying multivariate polynomials using Schönhage/Strassen

Question: I would like to ask the community where my following suggestion for an asymptotic bound for the running time of multiplying two multivariate polynomials using theorem $8.23 $ recursively ...
5
votes
1answer
129 views

From Primitive Recursive to Recursive by Iterating over more than one Argument?

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)? If so, then consider the following. Primitive ...
0
votes
0answers
39 views

P vs NP: Is there a “mathematical” way to state it?

If I wanted a statement of the Riemann Hypothesis, I could say the prime counting function pi(x) satisfies such and such an analytical approximation. If I wanted a statement of the P vs NP problem, ...
0
votes
1answer
107 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
2
votes
1answer
56 views

Tensors in matrix multiplication algorithms

Fast matrix multiplication algorithms, be it the Winograd and Coppersmith algorithm or any further improvement of it, extensively use tensors. In fact, the entire construction is based on tensor ...
0
votes
0answers
28 views

Is this general variant of nim NP-hard to decide who has a winning strategy?

Suppose there are $n$ piles of stones, where pile $i$ originally has $m_i$ stones, and each pile has a maximum number of stones $k_i$ that can be taken on each turn. Fix integer $N \geq 1$. Suppose ...
0
votes
1answer
38 views

Program languages recommended for complexity theory

I am an undergraduate studying mathematics and one of my interests include complexity and computability theory. I have no experience in programming. The computability theory books I looked into didn't ...
0
votes
0answers
31 views

Shrink wrapping algorithms to make a mesh watertight for 3d printing

I'm investigating algorithms to make a mesh watertight for 3d printing. I'd be very excited to implement such algorithms. The initial input is a mesh which is not watertight and I want to understand ...
2
votes
1answer
42 views

Are there any “proof schemes” for P $\neq$ NP?

Let me contextualize the title to make myself clearer: thanks to Cook–Levin theorem, there is a well known, and easy to understand way to prove that $P = NP$. It is known that if one can prove that an ...
0
votes
1answer
42 views

Lower bound on circuit size of a Boolean function

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
1
vote
1answer
84 views

Bilinear maps and Bilinear algorithms

How can one intuitively understand the definition of a bilinear map? Is there some way of looking at it geometrically? I found the following definition: Let $\mathit{A}$,$\mathit{B}$,$\mathit{C}$ ...
1
vote
1answer
69 views

Strassen's Algorithm for matrix multiplication

Can someone demonstrate the multiplication of two $4\times 4$ matrices using Strassen's algorithm? I don't understand when to stop partitioning the matrices. We first partition the two $4\times 4$ ...
1
vote
2answers
40 views

Computational Complexity

"Why are additions known to be cheaper than multiplications?" In contexts pertaining to algebraic complexity theory, this statement is often cited. Can someone elaborate on this? I don't understand ...
0
votes
0answers
35 views

Minimum vertex cover of two edge disjoint perfect graphs

How well can the minimum vertex cover of the union of a perfect graph and bipartite graph (the two graphs are edge disjoint but not vertex disjoint) be approximated?
0
votes
0answers
37 views

Time complexity of finding first eigenvector

What is the time complexity of finding the first eigenvector (the one that corresponds to the largest eigenvalue) of a positive definite matrix? In my application, that matrix is a Markov transition ...
1
vote
1answer
57 views

Please help understand how $ax^2+by-c=0$ is NP Complete

I found a statement that $ax^2+by-c=0$ is NP Complete. However I am unable to find any document showing the proof. There is a paper on few pay-walled sites but they are out of reach for me. The ...
0
votes
0answers
23 views

How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
0
votes
3answers
65 views

How to prove or disprove $n^{28} = O(2^n)$

Prove or disprove $n^{28} = O(2^n)$. My solution: $$\lim _{n \to \infty} \dfrac {2^n} {n^{28}} = \dfrac {2*2*2 \dots _{(n \ times)}} {n * n * \dots _{(28 \ times)}}$$ As $n \to \infty$, both the ...
0
votes
1answer
88 views

Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items. The algorithm works using the recursive formula of the binomial coefficient ...
0
votes
0answers
47 views

Multiplications in determinant of an $n \times n$ matrix?

Assuming we use Gaussian Elimination/LU decomp, is there a general formula to describe the number of multiplications involved in finding the determinant of an $N \times N$ matrix? Find the ...
0
votes
0answers
18 views

FPT algorithm equivalent definitions

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ ...
3
votes
2answers
49 views

Computational Complexity of Primality Checking

"PRIMES in P" proved that primality checking is in $P$. However, the CS 101 prime checking algorithm is to divide a number $n$ through all integers up to ${\sqrt n}$ , and if no results are whole ...
0
votes
1answer
46 views

Prove $K_4-Cover$ is NP-Complete

I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams. I have come across this problem and I'm having some difficulty with it: Let $ G ...
2
votes
1answer
40 views

Computation of permanents of general matrices

In the following paper http://www.stat.uchicago.edu/~pmcc/reports/permanent.pdf it is stated that: "Exact computation of permanents of general matrices is a #P (sharp P) complete problem, so no ...
2
votes
0answers
73 views

Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns) [closed]

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...
2
votes
1answer
95 views

Find the sum of all primes smaller than a big number

I need to write a program that calculates the sum of all primes smaller than a given number $N$ ($10^{10} \leq N \leq 10^{14} $). Obviously, the program should run in a reasonable time, so $O(N)$ is ...
0
votes
0answers
19 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
39 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
40 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
13 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} ...
13
votes
3answers
789 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:- ...
1
vote
0answers
31 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
26 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 ...
0
votes
0answers
24 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
70 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
22 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 ...
2
votes
1answer
37 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 ...
0
votes
1answer
50 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 ...
2
votes
0answers
72 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 ...