# Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

2,662 questions
Filter by
Sorted by
Tagged with
22 views

### Prove decidability or undecidability of a language accepted by a turing machine.

consider this problem: "Given a TM $X$, determine if the language accepted by $X$ contains more than $100$ strings" Is this problem decidable or not? Opinion 1: (mine) I derived my proof by ...
59 views

### What is the best computational software(free/cheap)? [closed]

I have already tried Wolfram Alpha (not pro) and I don't know whether I can access MATLAB for free, any software than downloaded for free and is easy to use will work. I need it for computing complex ...
66 views

### Can anyone help me verify if this prime sieve is going to work ? Also, can anyone help me determine whether this has high computational efficiency?

Here's a link to my conjecture : Quora - My New Prime Number Sieve Here's the content: A New Prime Sieve ! Hello there ! I think I’ve found a way to find prime numbers ! (Not a function, but a ...
30 views

### Freshman's dream over multivariate polynomial rings

I'm working on a project where I am trying to manipulate vandermonde matricies with entries that are monomials $M_t \in \mathbb{F}[x_1,\dots x_n]$. I am trying to equate this with another vandermonde ...
38 views

### Recursion for Characteristic Polynomial - Proof?

In the book "Computational Complexity of Counting and Sampling" I have found the following theorem: It gives a recursion formula for a division-free algorithm for the determinant in $O(n^4)$...
29 views

### Find the longest subinterval of [0,1] with a finite number of queries

We have a number of intervals (either finite or infinite), not overlapping if not for their extreme points, which union is [0,1]. One of them is long at least 1/4, and all the others are not longer ...
13 views

### algebraic branching programs and the 3x3 permanent

Using Grenet's construction (http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=193FC514DC541C17E8F03A7A6BDE4C61?doi=10.1.1.717.4014&rep=rep1&type=pdf ) we can write the 3x3 permanent as ...
29 views

### Is mathematical proof itself NP-hard? [closed]

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
15 views

I have a pentadiagonal symmetric matrix , with elements on the diagonal, on the 1st upper-diagonal and 1st lower-diagonal and at the n-th upper and lower diagonal. ( n changes values from one matrix ...
32 views

### Computational complexity of a modified Euclidean algorithm

The Euclidean algorithm computes the $\gcd$ of two integers with the recursive formula $$\gcd(a,b)=\gcd(b,a\bmod b)$$ and takes at worst $\log_\varphi(\min(a,b))$ steps, where $\varphi$ is the golden ...
18 views

### Understanding the protocol of Hsiao-Ying Lin and Wen-Guey Tzeng

I am trying to understand the solution proposed by Hsiao-Ying Lin and Wen-Guey Tzeng to Yao's Millionaires' Problem. Correct me guys if I am wrong but from what I have understood so far from the two ...
15 views

### Order to bound Taylor expansion error: not as straightforward as it seems.

Suppose we have the function $f(x) = e^{x}$, and we choose $0<x/r<1$. The Taylor expansion is $$f(x/r) = \sum_{k=0}^\infty \frac{(x/r)^k}{k!}.$$ If we truncate the series at order $K$ then the ...
36 views

### overall complexity of an algorithm

Is the following way of thinking correct? Assume one has some Algorithm, which for some fixed integer $n$ and some $i = 1,\dots, k$ has computational complexity $O(i\times n^{2})$. Assume I have to ...
21 views

40 views

### Are P, NP, PSPACE, and NPSPACE complexity classes?

In Ullman's Introduction to Automata Theory, Languages and Computation, the union theorem (Theorem 12.15) says Let ${f_i(n) | i = 1, 2, ...}$ be a recursively enumerable collection of recursive ...
26 views

### Measure of the relative complexity of equations

Is there some measure to compare, in a straightforward way, the complexity of equations? Complexity seen as a function of basic operations involved for solving the equation, or as any other intuitive ...
2k views

### How do we know that the P versus NP problem is an NP problem itself?

I have been doing some research on the P versus NP problem. On multiple occasions, I have seen people say that the problem itself is an NP problem. I have been curious about how we know this. If we ...
15 views

33 views

36 views

### Is this formula related do bynomial coeffient true? [closed]

i have found this relation in my complexity theory exercise, i would like to know where does this formula come from: $${{n}\choose{k}}\approx{n^k}$$ Thank you :)
17 views

### Heuristic for Turing Completeness?

I seem to recall that determining whether a language is Turing complete is an undecidable problem in general, but I was wondering what would work as a rule-of-thumb heuristic that strongly suggests it....
14 views

### Number Field Sieve complexity in Big-O-Notation

In the paper Pollard J.M. (1993) Factoring with cubic integers. In: Lenstra A.K., Lenstra H.W. (eds) The development of the number field sieve. Lecture Notes in Mathematics, vol 1554. Springer, Berlin,...
149 views

### Does the Riemann hypothesis guarantee that integer factorization is difficult?

In an exchange of comments at Is there any mathematical conjecture that is successfully applied in the real world in spite of being yet unproven?, user R.J. Etienne claims that RH guarantees that ...
32 views

### Which can be calculated faster? (Fast Fourier Transform)

I am introducing myself in what is Fourier analysis, solving some exercises I ran into a problem that made me curious. Since I don't know much about mathematical formalism, I approached the problem ...
121 views

### Most effective algorithms for each step of the basic RSA-Algorithm

I can't seem to find a detailed complexity/runtime analysis of the basic RSA-algorithm from Volker Heun's Book "Fundamentale Algorithmen" on page 275 or any other books which describe it similarly: ...
25 views

### Rice theorem and trivial properties for decidability proof

I'm going to have a complexity theory exam and i understood the importance of Rice theorem in proving if given a language $L_{p}=(L|L\space satisfies\space the \space property\space\space p)$, is ...
23 views

### Growth rate of integration

Let $f,g:[0,\infty)\to [0,\infty)$ where $\int_{0}^\infty g(x)dx<\infty$. Is it possible to find $f,g$ such that $$\frac{\int_0^a f(x)g(x)dx}{f(a)\int_a^\infty g(x)dx}$$ grows exponentially on $a$? ...