# Tagged Questions

Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$ ...
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$ ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
46 views

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, ...
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 ...
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 ...
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 ...