Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
1answer
67 views

what is a closure (hull) operator?

Just that. what is a closure operator? reading the wiki wasn't enough and i would like to know more. I'd be happy if someone shared examples of closure operators so that i may further understand ...
8
votes
2answers
95 views

Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?

I want to write a function that does the following: Input: An integer $n$ A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
1
vote
1answer
302 views

how discrete mathematics is related to computerscience

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
1
vote
1answer
209 views

How to deduce the psition mapping of entries of a matrix?

I would be thankful if any peer shed light on me. Assume that the mapping of a set is unknown. By knowing n number of E element sets and the transformed sets with positioned elements, How can I ...
0
votes
0answers
35 views

Complexity of index calculus method

I read somewhere that complexity of index calculus method which calculates discrete logarithm over $Z_p^*$ is $O\left(e^{(1 + o(1))(\sqrt{ln(p)\times ln(ln(p))}\;)}\right)$. My question is, why ...
1
vote
0answers
65 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
2
votes
2answers
54 views

Question about what it means to be in “NP”

Suppose I am trying to prove language $L$ is in NP. Does it suffice to construct a nondeterministic Turing machine that accepts all strings in the language in polynomial time? Or must the machine ...
0
votes
0answers
88 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
70 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
0
votes
1answer
66 views

efficiency of verifier of Boolean

For a Boolean expression formula φ, For a binary literal $i∈(0, 1)^l $ V(φ,i) is an Turing algorithm which decides whether i satisfies φ or not ...
1
vote
1answer
47 views

Denesting Logarithmic expressions

$\log_7(\log_2(3)) + \log_7(\log_5(6)) + \log_7(\log_{11}(1/2)) = \log_7(-1) + \log_7(\log_5(3)) + \log_7(\log_{11}(6))$ This can only be simplified by using the sum to product rule and noticing that ...
9
votes
3answers
200 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
6
votes
2answers
1k views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
0
votes
1answer
208 views

Proving By reduction from the Halting Problem

I want to solve the following exercise in Computability and Complexity Theory: By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable. ...
2
votes
1answer
73 views

knapsack with only odd elements

Is it feasible to solve the subset sum problem if all the elements are odd and we also know that whether odd or even no. of elements are used to form the sum for example - If i have the set -{ 9, 13 , ...
2
votes
2answers
255 views

transform traveling salesman problem into subgraph isomorphism problem

Lets say, I could solve subgraph isomorphism problem in constant time. How could I use this to solve traveling salesman problem? aka... how to transform traveling salesman problem into subgraph ...
1
vote
1answer
88 views

Big $\mathcal{O}$ notation for multiple parameters?

The following is an excerpt from CLRS: $\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
2
votes
0answers
63 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
1
vote
0answers
78 views

Expansion in powers

Let $n=2k, k \in Z_+$. Let $$P_k\left(\frac{t}{\sqrt n}\right)=n!\sum_{\begin{smallmatrix} n_1+\ldots+n_k=n \\ ...
0
votes
1answer
123 views

understing Cook theorem and input length

Following is my understanding of Cook theorem. Let P be a $\mathcal{NP}$ problem. And let M be a polynomial NDTM for P, $$ M(x) = \left\{ \begin{array}{ll} 1\text{ if x∈ P}\\ 0\text{ ...
2
votes
1answer
276 views

Proving that a function is negligible

In mathematics, a negligible function is a function $\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$, ...
1
vote
1answer
108 views

Restricted partitions?

Suppose I have an integer N and i want to partition it, it must only involve numbers in set $S$ and the number should appear only once. For example if $N = 12$ and $S = \{3, 5, 7\}$ the answer should ...
0
votes
1answer
288 views

Solving a recurrence relation using Z transform

I'm trying to solve the following recurrence using Z transforms: For $n\in \mathbb{N}^{*}$ $T(n)=1\ for\ n< 4$ $T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq ...
2
votes
2answers
118 views

Would it be possible to concoct a “harmful” axiom?

Suppose I run an automated theorem prover. It begins with the axioms of ZFC, and using a random number generator, it proves more theorems, and it runs for two days. At the end of the second day, it ...
3
votes
1answer
59 views

Computing the period of a fraction polynomial in the number of digits

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
6
votes
1answer
71 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
1answer
117 views

algorithm and Cook theorem

Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs. $x\in A$ if and only if for $i\in N$ $x(i)=0$ or $x(i)=1$ ...
0
votes
1answer
179 views

About Cook–Levin theorem

I want to check whether I understand the Cook-Levin theorem fully (using the Travelling Salesman Problem as an example). Given a weighted graph $G$ and an number $L$, the a Travelling Salesman ...
1
vote
2answers
56 views

Confusion related to P and NP problems

I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
1
vote
1answer
727 views

What does it mean for a function to be polynomially bounded

There is a definition in my notes and says, When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in ...
2
votes
1answer
125 views

Games for which the Lemke-Howson algorithm provides incomplete results

I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria ...
1
vote
1answer
279 views

Well formed formulas of all mathematical proof

Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory. However I have still question. For the operation ...
0
votes
1answer
98 views

Array resize problem

I need help with this problem if anyone can help. Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then ...
0
votes
1answer
32 views

Resizing array problem

I need some help with this problem. Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the ...
2
votes
2answers
198 views

Automated proof-checking machine

In the future, theoretically, is it possible to make an automated proof-checking machine? It means, given mathematical axioms and definitions, the computer can decide that a proof is correct or not, ...
0
votes
1answer
146 views

Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$ To solve this and find a Θ bound, i tried the following: I ...
1
vote
2answers
89 views

The use of master theorem appriopriately

I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is: $$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$ Can i use the master theorem in that relation? If ...
1
vote
2answers
68 views

Sequences and Languages

Let $U$ be the following language. A string $s$ is in $U$ if it can be written as: $s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$, where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
2
votes
1answer
65 views

How is naive CLIQUE algorithm polynomial time?

I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is ...
4
votes
2answers
87 views

How to recover a shuffled matrix

Suppose that I have a matrix $A$. $A$ can be a rating matrix. That is, $A(i,j)$ is the rating user $i$ has given to item $j$. Suppose that I shuffle the rows and columns of matrix $A$ and get ...
2
votes
1answer
45 views

What's the relationship between the Ham Sandwich Theorem and the PPAD Complexity Class?

Wiki says: "The Ham sandwich theorem is known to lie in PPAD but it remains an open question as to whether or not it is PPAD-complete." What is the computational problem based on the Ham Sandwich ...
1
vote
2answers
784 views

Time complexity of a modulo operation

I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this? A ...
1
vote
2answers
712 views

Solving a recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master ...
0
votes
1answer
150 views

Solving $T(n)=4T(\frac{n}{2})+n^2$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
3
votes
0answers
139 views

$\sum _{i=1}^{n} \sum _{j=1}^{n} \sum _{k=1}^{n}\sum _{l=1}^{n} A(i,j)A(i,k)A(i,l)A(j,k)A(j,l)A(k,l) $

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum _{i=1}^{n} \sum _{j=1}^{n} \sum_{k=1}^{n} A(i,j)A(j,k)A(k,i)$, where A(i,j) is the a ...
3
votes
1answer
749 views

How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$

I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
2
votes
1answer
61 views

How big is $Z_n^*$?

I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. ...
0
votes
1answer
48 views

Verifying reasoning: $2^{(10\log n + n/2)} = \mathcal{O}( 2^n)$

As the title states, why is $$2^{(10\log n + n/2)} = \mathcal{O}( 2^n)$$ The reason given via the solutions is, where $f_2(x) = 2^n$ and $f_3(x)=2^{(10logn + n/2)}$, If $c$ is any constant and ...
3
votes
1answer
86 views

Factorization of integers - why does it suffice to consider squarefree instances?

I sat a lecture where a proposition is proven that states the following: If computation of $(k!)_{k\in\mathbb{N}}$ is "easy", then integer numbers can be factored in non uniform polynomial time. ...
3
votes
1answer
61 views

Logarithm, its algebraic properties and algorithmic complexity (MIT OpenCourseware 6.042)

Does $$2^{\log{n}} T(n / 2^{\log n}) = 2^{\log{n}} T(1)?$$ If so, how? Also, I don't understand how the following equality works: $$\sum_{i=0}^{\log(n) -1}{2^i} = 2^{\log n} - 1$$ I'm afraid I'm ...