Computational complexity, a part of theoretical computer science.
0
votes
0answers
51 views
Its just one point… How do I find it?
Okay so here is the deal...
I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$)
and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$
where $0 \le ...
0
votes
0answers
37 views
How to find the nearest power product?
We call power products the integers of the form $x^m*y^n$ for $m$, $n$, $x$, $y \in \mathbb{N}$.
Given a number $u \in \mathbb{N}$, find the closest power product.
How does one solve this ...
0
votes
0answers
18 views
Pseudo inverse of matrix: SVD vs $A^{T}(A.A^{T})^{-1}$
For a C++ implementation I have to calculate Moore Penrose Inverse (AKA pseudo inverse) of non squared matrices. I was wondering ...
2
votes
2answers
76 views
COMPOSITE $\in$P if and only if PRIME $\in$ P
Let COMPOSITE be the following decision problem.
COMPOSITE
Input:
an integer $n \geq 2$.
Question: is n composite?
Show that
COMPOSITE $\in$P if and only if PRIME $\in$ P.
I think ...
2
votes
3answers
223 views
Factoring extremely large integers.
The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
1answer
41 views
Doubts related to set cover NP complete problem
I am trying to show that a problem is ${\sf NP}$-complete by reducing Set Cover to it.
I have three sets, say
$A = \{1, 3\}$,
$B = \{1\}$ and
$C = \{1, 2\}$.
In my problem, I need to find the ...
0
votes
1answer
24 views
Finding average-case time complexity
I have an integer array and some x integer number. I'm looping through this array and compare each element with x, if there exists the exact element, the algorithm ends.
The best case is B(n) = 1, ...
0
votes
0answers
37 views
Prove a function is computable in polynomial time
I am learning Complexity theory. I read a question on Arora book that I cannot solve. The problem is number 6 in Chapter 3, as follow:
Prove that the function H defined in the proof of Theorem 3.3 ...
0
votes
1answer
39 views
algorithm to determine complexity of algorithms?
Given a decision problem X, can there exist an algorithm A which, given any algorithm B which solves X in finitely many steps, determines whether B runs in polynomial time? If such an A exists, when ...
0
votes
1answer
33 views
Integer Linear Programming (ILP): NP-hard vs. NP-complete?
I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind.
It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
1
vote
2answers
38 views
Problem understanding a proof
In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there's this example:
Choosing an integer $a \in_R \{0,\dots,n\}$ using random bits.
We assume that we ...
1
vote
0answers
18 views
How did we arrive at this form of Markov's Inequality in this proof?
In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($ \textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), ...
0
votes
1answer
30 views
Clarification on some mathematics formula
In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a theorem on $\textbf{BPP}$ where I don't understand a few steps of its proof, it's totally independent ...
2
votes
1answer
36 views
“Certificate” in the context of computational complexity
I can't find any definition for the word either in the book I am reading or online. What exactly does certificate mean in the context of computational complexity? For instance:
[...]The above ...
1
vote
1answer
45 views
Some problems about the proof of a theorem
There's a theorem in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) where I don't understand some parts of its proof:
THEOREM: Suppose $f \in \mathbb Z[x_1,..., x_n]$ has ...
0
votes
1answer
22 views
Input size measurement according to polynomial presenation
There's a paragraph in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) that I don't fully understand:
Let $\mathbb Z[x_1,\dots,x_n]$ denote the set of polynomials in n
...
4
votes
1answer
74 views
Applications of computation on very large groups
I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
3
votes
1answer
578 views
what is the computational complexity of solving a quadratic program with linear inequality constraints
I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
1
vote
1answer
34 views
Greedy Optimized Subset-Sum Problem
Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible.
How do I show that there is a greedy algorithm to this ...
1
vote
0answers
49 views
0
votes
1answer
32 views
Complexity of Code Snippet Without Knowing A Function?
I have the code snippet:
int const n = 300;
int nArr[n];
for(int i = 0; i<n; i++) {
if(i >x)
copyPrevious(nArr,i);
}
I need to find the complexity ...
1
vote
1answer
47 views
What is the complexity class for each one of the following functions
What is the complexity class for each one of the following functions:
$a) (n^3+n^2 \log n)(\log n+1) + (10 \log n+7)(n^3+3)$
$b) (2n + n^2)(4n^3 + 4n)$
$c) (n^n + n2^n + 3n)(n! + 6n)$
1
vote
0answers
44 views
Calculate the time complexity for the following Travelling Salesman problem algorithm
Consider the following algorithm for solving the TSP:
$n$ = number of cities
$m$ = $n\times n$ matrix of distances between cities
min = (infinity)
...
1
vote
1answer
33 views
Binary search complexity
In sorted array of numbers binary search gives us comlexity of O(logN).
How will the complexity change if we split array into 3 parts instead of 2 during search?
0
votes
4answers
66 views
Big-O: Prove $2^n$ is $O(n!)$ [duplicate]
I am a little stuck trying to prove that $2^n$ is $O(n!)$. Obviously, I can tell in a few ways that this is the case. For one, based on Big-$O$ hierarchy, the exponential is beneath the factorial in ...
0
votes
1answer
31 views
Hardness of a special case of maximum matching
Input:
A set of N Users $\{u_1, ..., u_N\}$. A set of M products $\{i_1, ..., i_M\}$.
Every pair $(u,i)$ is associated with the probability of u purchasing the product i, $p_{u,i}$.
Task: Assign ...
2
votes
1answer
51 views
Computational complexity of unknotting problem?
The Wikipedia article on the unknotting problem says "a major unresolved challenge is to determine [...] whether the problem lies in the complexity class P". It mentions some work towards this result ...
2
votes
1answer
73 views
calculating the determinant of an $n \times n$ integer matrix
I want to write a polynomial algorithm for calculating the determinant of an $n \times n$ integer matrix. There are various codes in different programming languages on the web but unfortunately I am ...
1
vote
2answers
101 views
Möbius function help
Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate ...
3
votes
1answer
63 views
Books on computational complexity
Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area?
I've heard a thing or ...
2
votes
1answer
51 views
2-colorable belongs to $\mathsf P$
To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
0
votes
0answers
62 views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Does it belong to P (the class of polynomial running time ...
52
votes
4answers
1k views
Complexity class of comparison of power towers
Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
0
votes
0answers
12 views
Computational Complexity of Tensor Decomposition
I am studying tensor decomposition techniques such as the CP model (a.k.a., PARAFAC), and the Tucker model.
My reference paper is "Tensor Decompositions and Applications".
I need a survey about the ...
0
votes
0answers
26 views
Time complexity of the described DTM
There is a DTM with alphabet $\Sigma = \{∗, 0, 1\}$, that on input $1^n$ outputs $1^n ∗ 1^n$. That is it takes a string of $n$ ones and replaces it by two strings of $n$ ones, separated by a blank ...
0
votes
0answers
45 views
How to calculate an orthonormal basis for a matrix?
Are there any specific, easy to compute, algorithms to build an orthonormal basis for a matrix in which each column has length one?
0
votes
0answers
37 views
How to prove that the hitting time for a random $(2,k)$-walk is $\mathcal{O}(\frac{k^4}{r})$?
I'm using the following definitions:
An $(x, y)$-partial-rectangle is a sequence of x integers $(i_1,i_2,\ldots,i_x)$ such that $0 \leq i_1 \leq i_2 \leq \ldots i_x \leq y$. One ...
1
vote
0answers
27 views
Algorithm for topological sorting without explicit edge list
Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
0
votes
0answers
30 views
Simulating an alternating Turing Machine
I'm trying to figure out this question:
Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...
1
vote
2answers
117 views
A Problem on Time Complexity of Algorithms
I want no know if the following problem is solved or not, or how can I solve it?
Problem: For every integer $t$, Is there any problem that can be verified in $O(n^{s})$ but its solution can be found ...
1
vote
0answers
19 views
Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)
I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
0answers
47 views
Homomorphical Equivalence is NP-complete
Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$.
The task is to prove that this decision problem ...
0
votes
1answer
37 views
Proving an equality
Let $f(n) = n^ {\log n}$. Let $p(n)$ and $q(n) \geq n$ be polynomials. I want to show that for
$n$ sufficiently large $f (n)$ satisfies
$$p(n) < f (n) < 2^{q(n)}$$
starting from the above ...
1
vote
1answer
14 views
Notation about a randomized max cut algorithm.
http://users.cms.caltech.edu/~mccoy/publications/teatalk1.pdf
I'm trying to understand the lemma in this.
So we have
Lemma
Let $r$ be a random vector. For any unit vectors $u_{i}$ and $u_{j}$,
...
1
vote
0answers
41 views
Help with Computational complexity of recurrence relation, Big Omega, Big O and Big Theta problem.
The problem that I am struggling with is the recurrance relation
T(n) = floor(T(n/2)) + ceiling(T(n/2)) + ceiling(n/2)
I am supposed to answer true/false to each of the following (along with ...
0
votes
0answers
23 views
Determining if a language is in P or NP?
Is the following language in P or NP?
EMPTY_TM = {⟨N⟩| N is a TM that accepts no input}
Can someone shed some light on how to come to such a conclusion also?
5
votes
1answer
85 views
Simplify $O(n^k/2^n)$
In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a way to even further ...
1
vote
1answer
29 views
Are these two context free grammars equivalent?
Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as:
S-->aaSb
S-->A
A-->aA
A-->a
Would it be equivalent to write this CFG as:
...
0
votes
2answers
90 views
Determine whether $x^3$ is $O(g(x))$ for certain functions $g(x)$.
a) $g(x) = x^2$
b) $g(x) = x^3$
c) $g(x) = x^2 + x^3$
d) $g(x) = x^2 + x^4$
e) $g(x) = 3^x$
f) $g(x) = (x^3)/2$
Do you guys have any ideas? Thanks!
1
vote
0answers
19 views
Does “short integer solution” lattice problem admit hard instances with q=2?
Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, ...
