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)

3
votes
0answers
14 views

Is this permutation-sum problem NP-hard?

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In ...
1
vote
2answers
61 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 ...
1
vote
0answers
31 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
24 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
29 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
15 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 ...
0
votes
0answers
25 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
49 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
36 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
73 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
31 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
14 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
35 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
8 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
32 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
29 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 ...
0
votes
1answer
46 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
40 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
28 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
22 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
19 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
54 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
16 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
58 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
30 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
35 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
8 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
37 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
42 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
34 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
56 views

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

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
72 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
14 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
17 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
28 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
12 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
733 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
26 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
20 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
18 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
46 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
19 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
22 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
34 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
33 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
52 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
15 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
0answers
53 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 ...
0
votes
1answer
48 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 ...