Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
votes
1answer
9 views

Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = i to n^2 do print (i, j).

for i = 1 to n do for j = i to n^2 do print (i, j). So here is what I've got $\sum_{i=1}^n \ \sum_{j=i}^{n^{2}} \ $ $C\sum_{i=1}^n \ \sum_{j=...
1
vote
0answers
52 views

Is any prime test verifiable?

Factoring a large number $x$ by trial division is a lot of work, but if you succeed, you get two factors, which anyone can easily multiply together to make $x$: an easily checked proof that $x$ is in ...
1
vote
0answers
21 views

Closest string attempted algorithm.

In theoretical computer science, the closest string is an NP-hard computational problem, which tries to find the geometrical center of a set of input strings. To understand the word "center", ...
0
votes
0answers
39 views

Finding the numerical listed string to the center algorithm.

Suppose we have a string that occupies a length of seven characters, and the number of strings altogether is ten. We include the hamming distance of three characters. If we calculate the exact amount ...
0
votes
0answers
11 views

Permutative Constraint on Image Approximation

Motivation I am trying to explore the idea of constraining the approximation of an image represented by an $m$-by-$n$ matrix $A$ by the values on a linearly-spaced interval of $mn$ elements $L$ ...
1
vote
0answers
31 views

Attempted algorithm to find which shortest permutation of a string out of “hard.”

Recently, I have been contemplating on how to find an unknown factorial. To find a particular string of text. Update- I removed pi. The formula Z is defined as L= length of string in character ...
0
votes
0answers
21 views

Extracting common roots of polynomials

If we have $2n$ (maximum possible) algebraically independent degree $2$ homogeneous system of polynomials with $\mathbb Z$ coefficients in $2n$ variables with exactly one integer root (up to sign) can ...
0
votes
1answer
16 views

Minimise computational cost for given level of MSE

I am trying to understand how to minimise cost of a Monte Carlo implementation for a given value of MSE/RMSE. Please see the notes attached...I do not follow the second line. I would be grateful if ...
0
votes
2answers
32 views

Fast Fourier Transform with Negative Integer Exponent

Given $f(x)=ax+b+\frac{c}{x}$ and $N$, I'd like to ask how to calculate $\sum_{i=1}^{N}f(x)^i$ efficiently using fast Fourier transform?
0
votes
1answer
18 views

Why does this definition of the 3-PARTITION problem imply that every set contains exactly 3 elements?

I have the following definition of the 3-PARTITION problem taken from this paper: https://www.sciencedirect.com/science/article/pii/0166218X93900853 Given $3m$ positive integers $a_1, a_2,...,a_{3m}$ ...
0
votes
0answers
22 views

Complexity of finding a common coprime element

Let $n_1,\ldots,n_u$ denote $u$ positive integers, all of which are bounded above by some integer $N$. Question: 1. How hard is it to find an integer $m$ $(1 < m < N)$ that is coprime to $...
1
vote
1answer
31 views

Using the reduction of 3-SAT to 3-COLOR, explain why complexity proofs by reduction work.

I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, ...
0
votes
1answer
30 views

approximation algorithm for TSP and P=NP

i recently read an article about approximation algorithms for solving the TSP problem. One of the first theorems in this article states: if there is an α-approximation algorithm for the TSP (...
0
votes
0answers
12 views

Polynomial reduction to $\Pi_2^p$

Suppose I have decision problem $L$ and $L'$ and $L$ is reducible to $L'$ in polynomial time. Suppose further, that $L$ is in $\Pi_2^p$ in the polynomial hierarchy. What can be said about the class of ...
0
votes
0answers
88 views

Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem

I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time. Link to the algorithm : polynomial time algorithm In that post, I presented ...
-2
votes
0answers
145 views

Thinking of boolean variables as sets, and $\mathbf{P=NP=co-NP}$?

This is an algorithm I came up with, that seeks to solve the 'Boolean Tautology Problem'(which is co-NP complete) in polynomial time, using $3-DNF$ clauses. I am posting this algorithm here seeking ...
0
votes
0answers
19 views

P and NP-complete in Sudoku

We know an $n$-Sudoku puzzle is with $n \times n$ subgrids consisting of $n \times n$ cells; you will fill it with numbers from $1$ to $n^2$. Candidate solution have size polynomial in $n$, and can ...
0
votes
0answers
24 views

a function that is not $o(n)$ but also no $\Omega(n)$

I need to find a positive function like this $$f(n) \neq O(n)\, \text{ and } f(n) \neq \Omega(n)?$$ We can define a function that for infinite number of input will take O(n^2) and for infinite ...
0
votes
2answers
34 views

Sum of functions is big Oh

I want to show that if $$ d(n) \in O(f(n)) \ \Rightarrow d(n) \le c_1*f(n) \\ e(n) \in O(g(n))\Rightarrow e(n) \le c_2 *g(n) \\ $$ then $$ d(n) +e(n) \in O(f(n)+g(n)) $$ Can I say that (A) $$ d(n) +...
0
votes
2answers
50 views

Complexity of a recursive algorithm on formulas of propositional logic

A proof I've seen on reductions for $\mathsf{NP}$-hard problems relies on evaluating the complexity of an algorithm computing a function which is defined recursively in the structure of formulas of ...
-1
votes
0answers
18 views

How to prove/disprove big theta problem

Was given an exercise to prove or disprove the following: $4^{k^2} \in \Theta (4^{k^2 + k}) $ any hints?
0
votes
1answer
27 views

Disproving Big-oh

How would you disprove the following: $ \exists k \in \mathbb{N}, n^n \in O(n^k) $. I am aware that I have to pick a value for $n \in \mathbb{N} $ that will give us $n^n > c*n^k$ but I can't seem ...
0
votes
1answer
50 views

Complexity of $n \sqrt{n}$

I know that $O(n\sqrt{n}) = O(n)$ but I have no idea how I can prove this. Can you give me a hint?
1
vote
1answer
24 views

Proving Big oh of $(k^5 - k^3)$

I am new to big oh notation and proofs and I can't really wrap my head around the proofs. I know how to prove that an expression is big Oh of a simple expression, lets say $k^2 \in O(k^5)$ but my ...
0
votes
0answers
20 views

Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)

Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds: $\forall t \in T(k,l): k \leq |t| \leq l$ $\...
1
vote
1answer
31 views

Number of different graphs with this degree sequence

The set of degree sequences in question is: $$ D_1=\{4^4,6^4,4^4\} $$ $$ D_2=\{4^4,6^4,6^4,4^4\} $$ $$ D_3=\{4^4,6^4,6^4,6^4,4^4\} $$ $$ D_4=\{4^4,6^4,6^4,6^4,6^4,4^4\} $$ $$ ... $$ $$ D_N=\{4^4,...
0
votes
0answers
13 views

How to prove {e: L($M_e$} is decidable} is not Turing-recognizable?

I have reduced {e:$M_e$ accepts e} to this one. But I failed to reduce in the other direction. And I don't know if there is an algorithm to solve this. Thank @Noah Schweber who tells me it's not ...
1
vote
0answers
17 views

Computational Complexity of A=PLU versus other methods

I am currently trying to understand how to wrap my head around the following problem - Consider solving $AX=B$ for $X$, where $A$ is $n\times n$, and $X$ and $B$ are $n\times m$. There are two ...
0
votes
1answer
30 views

Prove the following big O: $n^2+n\log n \in O(n^{3/2})$

Prove the following big O: $n^2+n\log n \in O(n^{3/2})$ I wanted to verify my proof: $n^2+n\log n \leq n^2 + n^2 \text{ (for all $n$)}=2n^2$ Then we want $2n^2 \leq c\cdot n^{3/2}$ which means $2/\...
1
vote
1answer
26 views

What does it mean for a set $A$ to be computably enumerable in another set $B$?

In my introductory computability class I keep seeing the phrase set $A$ computably enumerable IN set $B$? I don't want a definition of computably enumerable, I know what that is, and there are a lot ...
0
votes
1answer
27 views

Expected running time to sort an array N using K mergesort on sub-arrays of N

I'm reaching out to this community today regarding a problem I found in a book and that I deem to be really interesting but that I have troubles solving. Assume that all the elements in the input ...
0
votes
1answer
46 views

Asymptotic growth rate of $T(n) = 8T(\frac{n}{2}) + \mathrm{n}^{\log_2 n}$

How would I go about finding the time complexity $ T(n) = 8T(\frac{n}{2}) + \mathrm{n}^{log_2n} $ ? I've tried applying Master Theorem (Case 3), but am unsure if I did it correctly. First, I set $ \...
1
vote
0answers
44 views

Modelling congestion games in python without tons of for loop

In the bidirected triangle network as shown below, 4 agents $\{s1,s2,s3,s4\}$ have their own destination $\{t1,t2,t3,t4\}$. I am trying to model this problem with a python script without any game ...
0
votes
1answer
18 views

Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = 1 to n do for k = 1 to i + j do print (i, j, k).

for i = 1 to n do for j = 1 to n do for k = 1 to i + j do print (i, j, k). So here is what I've got $\sum_{i=1}^n \ \sum_{j=1}^n \ ...
1
vote
0answers
16 views

What is the current fastest algorithm for finding the maximum common subgraph?

First of all, it's my first time at this sub StackExchange so, my apologies if I'm making some newbie mistake when asking this question. I'm currently researching algorithms for finding the maximum ...
0
votes
0answers
37 views

A practical algorithm for finding distances of a set of strings?

Having nothing to do today stuck at home I came up with an idea to use an input from a set of strings of the same length. I'm devising an algorithm that takes the strings and sees which string has the ...
0
votes
0answers
78 views

Complexity of a copy and reverse Turing Machine

I have a turing machine, that appends a reversed copy of a string to the end of the string. The alphabet of the TM is {a, b}. Copy & Reverse TM How can I prove the time complexity of this Turing ...
2
votes
1answer
46 views

What is the computation complexity of calculating the exact sum?

What is the computation complexity of calculating the exact sum of the finite series $$\overset{\sqrt{n}}{\underset{i=2}{\sum }}\frac{n}{i}$$ ? It can be seen that we need $\ \sqrt{n}-1\ $ ...
0
votes
1answer
20 views

Determine the number of basic steps required in the following algorithms in big-oh notation

The book doesn't quite explain how to do this. I tried looking at the notes my teacher gave me, but it's an easier problem than what the book shows. I've been staring at the book for about an hour ...
0
votes
0answers
12 views

computational complexity of Inverse perspective mapping

can anyone confirm the computational complexity of IPM (inverse perspective mapping)?enter image description here EQUATION 1 AND 2 I mean (Big O ) of 2 equation 1 and 2 in the image
1
vote
0answers
30 views

Number of $S_n$-orbits in $P^k(\{1,\dots,n\})$

Let $n$ and $k$ be integers with $n\ge1$, $k\ge0$, and let $a(n,k)$ be the number of orbits of the symmetric group $S_n$ on the $k$-th iterated power set $$ P^k(\{1,\dots,n\}) $$ of the set $\{1,\...
2
votes
1answer
77 views

What is the Computational Complexity of the Elementary Symmetric Polynomials

The elementary symmetric polynomials in $n$ variables, $e_k(X_1,\dots,X_n)$, are defined implicitly by $$(X-X_1)(X-X_2) \cdots (X-X_n)=\sum_{k=0}^n (-1)^k e_k(X_1,\dots,X_n) X^{n-k}, \quad 1 \leq k \...
1
vote
1answer
41 views

Using the substitution method on $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$ [duplicate]

My task at hand is to find a tight asymptotic upper bound for the recurrence $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$. My initial idea has been to substitute $m=\lg n$ and define a new recurrence $s(m)=p(2^...
2
votes
2answers
60 views

$T(n) = T(\sqrt{n}) + \sqrt{n}$ solving recurrence

$T(n) = T(\sqrt{n}) + \sqrt{n}$ I would like to try solving this recurrence in big-O/$\Theta$/$\Omega$. My first idea was to take $n = 2^m$ so: $$T(2^m) = T(2^{m/2}) + 2^{m/2}$$ Which we rewrite as: ...
0
votes
0answers
44 views

Eigenvalues for matrix with particular structure

I have a square matrix of the form: $$ \begin{pmatrix} a & b \\ -b & a \end{pmatrix} $$ where $$ a = \begin{pmatrix} D1 & t & 0 & 0 & t & 0 \ldots t \\ t&D2&t&...
1
vote
0answers
27 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
0
votes
0answers
20 views

Proof of #P-completeness of the number of simple paths in a simple graph

I have a simple non-directed graph and I am trying to find an algorithm to solve the number of simple paths that are possible. The problem is that I have seen in some forums that this problem is #P-...
0
votes
0answers
13 views

Complexity of A*-lasso algorithm (dynamic programming)

Consider Algorithm 1 in the Xiang & Kim (2013) paper known as A*-lasso for learning Bayesian Networks structure problem which is an NP-hard problem. It seems to me that Algorithm 1 has a ...
2
votes
1answer
49 views

Reduction from 3-SAT to MAX 2SAT

For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an ...
1
vote
1answer
102 views

Count of disjoint combinations of sets of sets

Is there a theorum or algorithm for counting the number of disjoint combinations of sets of sets with a time complexity better than $O(n^k)$? Given $f(\mathbf{S},k)$ is the function to count the ...