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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Optimizing over disjoint sets

Given a set $j \in J$, a set $i \in I$, positive coefficients $C_j$, positive values $w_{ij}$. For each $j$ find set of values of $i$, $I_j$, such that $\sum_{j \in J} C_j (1- \sum_{i \in I_j}w_{ij})^...
  • 154
0 votes
0 answers
12 views

How to give a zero-knowledge proof for G3C being NP-complete

I watched a YouTube video where Avi Wigderson explained his work on zero-knowledge proof. He mentioned that all mathematical statement that has a proof has a Zero-Knowledge Proof. I also read the ...
0 votes
0 answers
11 views

Can satisfiability (2 SAT) indicate whether a bad loop is possible in an implication graph?

I have found that these clauses are satisfiable: {a,b},{b,¬c},{c,¬a} Can I then assume that a bad loop is not possible? Because I have found that it would be possibel to go from b to b, or would this ...
  • 1
-1 votes
0 answers
10 views

Will proving NL = co-NL also prove the Immerman-Szelepcsényi theorem? [closed]

I wondered if I could prove NL = co-NL, does it immediately lead to the fact that NSPACE(s(n)) = co-NSPACE(s(n)) for s(n) ≥ log n (the Immerman-Szelepcsényi theorem)? If so, could someone briefly ...
  • 1
0 votes
0 answers
16 views

Time complexity of bitwise addition

For example, the bit length of $a$ is $s$ and bit length of $b$ is $t$. Assuming $s>t$. Wondering what the running time of $a+b$ is in $s$ and $t$. I know this is answered in another thread but I ...
1 vote
0 answers
27 views

Equation that, when the input increases by a factor of 10, the growth rate of the output increases exponentially

I did some performance testing on one of our pipelines at work, feeding in batches of records at increasing factors of 10. I noticed that at every increase, the growth rate of the runtime ...
0 votes
0 answers
10 views

Are these two definitions equivalent? "Appropriate" and Time-Constructible functions

My lecture notes define a function $f$ as "appropriate" if: $f$ is an increasing function $\exists$ a $k$-tape Turing machine $M$ with alphabet $\Sigma$ such that, given $x \in \Sigma^\star$...
0 votes
0 answers
23 views

Sparse matrix multiplication

I know that sparse matrix multiplication refers to multiplying a matrix by a vector, where the matrix has mostly zeros as its entries. However, my question is, can we say we have sparse matrix ...
0 votes
0 answers
10 views

Prove that language is NP-Complete [closed]

Prove that language A = {ϕ | ϕ - 3CNF formula, there exists a set of literals such that exactly two of literals in each clause are true } is NP-Complete
0 votes
0 answers
10 views

Is there a way that can feasibly turn a Boolean formula to a conjunction of equivalences while maintaining equisatisfiability?

By "feasibly", I mean the length of the output and the time it take is linear. And by "conjunction of equivalences" i mean formulas of the form $x_1\leftrightarrow f_1(x_1,\dots,...
0 votes
0 answers
17 views

Complexity of multivariate integration

I was reading this question regarding the complexity of integrating over a multivariate distribution. The statement is that it is NP-Hard, that is there is no polynomial-time algorithm to solve the ...
  • 154
-1 votes
0 answers
33 views

Show that SQRT is NP-complete

SQRT = $\{(a, b, c): \exists x > 0, x < c: x^2 \equiv a \pmod{b}\}$. I need to show that this language is NP-complete, so I need to be able to show that $A \leq_p SQRT$ for any NP-complete A. ...
0 votes
0 answers
62 views

Complexity of $x+\log x+\log(\log x)+...+\log(\log(\log(...(\log x)...)))$

Formally, we define a sequence of functions $(f_n)$ such that $f_0(x) = x$ and $f_{a+1}(x) = \log(f_a(x))$. What is $$\text{O}\left(\sum_{i=0}^n f_i(n)\right)?$$
3 votes
0 answers
88 views

An Integer Factoring Algorithm using quadratic residues modulo $p_i$

Background: I had previously asked this question and received a comment that it isn't worthwhile analyzing an algorithm that is sometimes slower than trial division. So, I had been working on a ...
  • 2,000
-1 votes
0 answers
10 views

Can someone explain how the Worst case time is calculated for this Graph?

[Text](enter image description here
  • 1
2 votes
0 answers
24 views

Efficient Approach to Order Vectors?

given $n$ binary victors which may include $\$$ sign like this: $101\$0111$ What's the most efficient algorithm to order those vectors in $nxn$ matrix such that in the main diagonal there is no $\$$ ...
  • 39
0 votes
0 answers
8 views

Distributing a value based on fractions where each participant has a maximum amount?

I have a saystem where I want to distribute a value to participants based on certain fractions: participant A 1 participant B 2 participant C 2 participant D 5 ...
0 votes
1 answer
31 views

How to Express Stacking Process of Vectors Mathematically

I have this multi-dimensional matrix (5 * 5): X= [ [ 1,1,1,1,1] , [2,2,2,2,2] , [3,3,3,3,3], [4,4,4,4,4] , [5,5,5,5,5]] I want to extract certain rows and columns ...
2 votes
0 answers
47 views

On Theoretical Bounds for Time Complexity of Integer Factoring

Is there a theoretical bound on how fast a classical integer factorization algorithm (i.e., non-quantum algorithm) can be? $$\begin{smallmatrix} {\text {Factorization method}} & {\text {Time ...
  • 2,000
0 votes
0 answers
30 views

Is the graph non-isomorphism problem in NP?

On Wikipedia, I've found that graph non-isomorphism is not NP-complete, but there is no information about it being in NP. If that's the case, what is the witness of two graphs being non-isomorphic?
  • 161
1 vote
1 answer
48 views

Computational complexity of $e^n$ which is $O(e^n)$, vs. $2^n$ which is $O(2^n)$

Is the Big-O of $e^n$ greater than the Big-O of $2^n$? I understand: We have a single time complexity class of exponential for $2^n$, $e^n$ and $4^n$ (if I am not wrong.) There is no real algorithm ...
0 votes
0 answers
20 views

Recurrence Relation, Iteration Substitution

$T(n):= \begin{cases} 7&\text{for}\, n =1\\ \pi \cdot T(n/ \pi) + n \log (n)&\text{otherwise}\ \end{cases}$ I have this so far: $T(n) = \pi[\pi \cdot T(n/\pi^2)+n/\pi \cdot \log (n/\pi)]+n \...
3 votes
1 answer
29 views

Upper bound on amount of "pieces" created by nested absolute values.

If I have a nested absolute value equation such as: y = |||3x-2|-|8-7x|| -2|x+3|| where all terms in absolute values are linear, what is the complexity (Big -O) of the upper bound on the amount of &...
4 votes
0 answers
85 views

Why do almost all points in the unit interval have Kolmogorov complexity 1?

I am reading Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, Journal of Computer and System Sciences, Volume 49, Issue 3, December ...
0 votes
0 answers
4 views

Double hashing space complexity

In double hashing if we select a second level hashing function (per CLRS): $ h_j(k) = ({(a_j \cdot k + b_j)} $ mod $ p ) $ mod $ m_j $ where $m_i = {n_i}^2$, where $n$ is the universe (number of ...
1 vote
0 answers
58 views

Isn't this requirement true for any Turing machine?

I came across this proof today and I can't figure out what the second restriction is supposed to mean (marked in red) - does it mean, that for every Turing machine, that if it stops for an input after ...
0 votes
0 answers
18 views

Why would the Turing Machine constructed by the proof of Posts Theorem be computably enumerable?

Good evening, I'm currently reading up about the Friedrich-Muchnik Theorem/Posts Theorem and will the construction makes sense, I can't really understand, why the construction would yield a computably ...
0 votes
0 answers
18 views

How can one decide this problem by using a halting-machine-oracle?

In the book I'm currently reading, there is the following set given: While I understand the reasoning behind the argument given, I could not figure out how to actually construct the necessary ...
0 votes
3 answers
64 views

Proof that $n^\frac{n}{2} \in \mathcal{O}(n!)$

In the context of Algorithm's time complexity, I'm trying to proof the following $n^\frac{n}{2} \in \mathcal{O}(n!)$ I'm aware of the following inequalities: $\left(\frac{n}{2}\right)^\frac{n}{2} \leq ...
0 votes
0 answers
5 views

Split matrix by groups of columns *but* capture all combinations

Say I have a big matrix, 50000 rows, 80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling). But I need to make sure every column can be combined with ...
3 votes
1 answer
38 views

A lemma in the proof of push-relabel maximum flow algorithm.

It is lemma 4.3, I have been thinking about it for 3 days. A detailed description is given below. In "A new approach to the Maximum-Flow Problem", 1988, by Goldberg, to prove the $\mathcal{O}...
2 votes
1 answer
61 views

Trick of selecting fundamental matrix in nonhomogeneous differential equations to simplify calculations

Problem: I came across the following differential equation set: $$ \begin{cases} \dot{x}&=3x-2y+t\\ \dot{y}&=4x-y+t^2\\ \end{cases} $$ My solution I followed normal practices and found the ...
2 votes
0 answers
47 views

How can there be non-computably enumerable sets in a computably enumerable degree?

I was just reading up about turing degrees and the part marked in red confused me: Screnshot of book page If there was a non computably enumerable turing machine that could be computed given the ...
0 votes
1 answer
13 views

Is finding the percolation threshold of an arbitrary continuum system P or NP complex?

By arbitrary I mean an infinite 2D system of e.g. 3 different sizes of rectangle like in figure 5 of https://doi.org/10.1103/PhysRevE.88.012101
  • 11
0 votes
0 answers
19 views

How to perform integral matrix with vector product in less than O(n^2)?

$$ \int_a^b e^{i \phi x}\left(e^{i \theta x}\right)^{\mathrm{T}} \bar{z} \,dx $$ where $\phi, \theta$ are $n$-dimensional vectors with elements between $-\pi$ and $\pi$, $i^2 = -1$, and $\bar{z}$ is ...
  • 1
3 votes
0 answers
74 views

Estimation the computation complexity of algorithm with more that one choice

The problem: We have a weighted graph $G=(V, E, W)$ with $|V| = n$, $|E| = n-1$ and $W$ is set of edge's weight. The graph $G$ includes one ring on $n_1 \geq 3$ nodes and $n_2$ isolated nodes, $n_1+ ...
  • 1,213
1 vote
0 answers
46 views

What's the best programming language for computing continued fractions? [closed]

I've been trying with Wolfram Mathematica, and for the most part it does the job well, but when computing higher amounts of numbers, it does take a while, hours, even days. So, I was wondering if ...
0 votes
0 answers
11 views

Efficient way to find pair of vectors minimize a special sum.

Given $k$ unique vectors $\mathcal{X} = X_1, \cdots, X_i, \cdots, X_n$. Where $X_i \in \mathbb{R}^k$. We want to find a pair of vectors $X_i, X_j \in \mathcal{X}$ such that this sum is minimized: $$ \...
  • 1,203
1 vote
1 answer
45 views

About the complexity of Pollard's p-1 method

I'm currently working on a project for a computational math subject, which is about different algorithms on factoring and I'm having a little problem with the analysis of the complexity of Pollard's p-...
0 votes
1 answer
26 views

How to determine computational efficiency of different formulas?

I am not sure whether or not the speed at which computers can compute a formula heavily depends on the calculating program or not. My question will assume there is a significant difference though, and ...
1 vote
1 answer
20 views

From combinatorial embedding to DCEL in linear time

The problem: We have a planar graph $G=(V,E)$ with $|V| = n$, given as input in the form of a combinatorial embedding. We want to build a DCEL (doubly connected edge list) in $\mathcal{O}(n)$ time - ...
-2 votes
2 answers
52 views

Determining if polynomial function despite no addition/subtraction or rasing to power

f1(n) = 100n Is the above function polynomial? I have examples of polynomial fucntions, but this one particularly I am not sure about since there is no addition or ...
0 votes
0 answers
20 views

Recurrence Relation and the corresponding pseudo-code

I run into an exercise from a book on "algorithms and data structures" that is giving me some trouble. I need to write the pseudo-code of a recursive algorithm regulated by the recurrence ...
0 votes
0 answers
30 views

Can we represent every element of a finite Boolean algebra by a string that is a polynomial of the number of atomic propositional variables in it?

If we store a finite Boolean algebra in n bits where $n$ is the number of atomic variables appearing in the algebra, can we somehow represent every element in the Boolean algebra by a string that is a ...
0 votes
0 answers
19 views

Show that 1POSCNF (a special case of CNF) satisfiability can be solved in polynomial time.

This is a question from the midterm exam of the Introduction to Computational Logic course I took just 2 hours ago. The question is as follows: A propositional logic formula $\phi$ is in 1POSCNF if $...
1 vote
0 answers
10 views

Kolmogorov $\epsilon$-entropy, $n$-width, and $\epsilon$-capacity and applications

What is the relationship between Kolmogorov $\epsilon$-entropy, Kolmogorov $n$-width, and Kolmogorov $\epsilon$-capacity of a set $M$ in a metric space $X$? (The $\epsilon$-capacity here is the ...
  • 49
2 votes
1 answer
19 views

Efficient way to verify if pair of numbers are medians of partition of sets

Given a multi-set of multi-sets $\mathcal{S} = \{S_1, \ldots,S_i, \ldots, S_n \}, S_i \subset \mathbb{R}$. Denote powerset of $\mathcal{S}$ as $\mathbb{P}(\mathcal{S})$. My question is, given a pair $(...
  • 1,203
2 votes
0 answers
69 views

Complexity of computing the homology of a finite topological space

$\textbf{Problem:}$ Given a finite topological space $X$ with $|X|=n$ and $k\in \mathbb{N}_0$, decide if $H_k(X,\mathbb{F})=0$. Where $\mathbb{F}$ denotes some field and one can also assume that $X$ ...
  • 183
1 vote
0 answers
21 views

Complexity of algorithms on graphs - Text request

What I'm looking for: A good text on graph data structures, algorithms, and their complexity - aimed at those interested in mathematics research (as opposed to, say, programmers). List of things a ...
6 votes
0 answers
148 views

Computational complexity and commuting functions

We have two functions: $$ f: \{0,1\}^* \to \{0,1\}^* $$ $$ g: \{0,1\}^* \to \{0,1\}^* $$ that commute: $$ f[g(x)] = g[f(x)] $$ These two functions can be calculated in polynomial time (in the length ...

1
2 3 4 5
66