5 votes
Accepted

How can one mathematically compute the security level of a human computable password schema?

I will teach you a heuristic for how to compute this, that is likely to get you a very accurate result. I will assume that the mapping from digits to digits is required to be bijective. Then there ...
user avatar
  • 2,695
4 votes

Permanent of a low-rank matrix is easy to calculate?

Alexander Barvinok gave an algorithm to compute the permanent of a rank $r$ matrix in $O(n^{r-1})$ arithmetic operations; see Theorem 3.3 in: Barvinok, Alexander I., Two algorithmic results for the ...
user avatar
2 votes

Computational cost/complexity of algorithms based on the number of mathematical operations

Algorithm A2 is clearly better, since it performs fewer mathematical operations. Which is far from true in the real world. Fewer operations is not equal to better, unless you assume that all ...
user avatar
  • 32.5k
2 votes
Accepted

Time Complexity of Modular Multiplication

I think you may be mixing up the bit-sizes. Naive multiplication (in both cases) requires time (and space) at most "the square of the number of bits in the representation". Numbers modulo $...
user avatar
  • 3,833
2 votes

Estimating the duration of a computationally-intensive process

You don't have many sample points, but I'll still share some speculations, just know that they're credibility may be jeopardized by lack of data. I plotted your data on a log-log time (sec) vs. size ...
user avatar
2 votes
Accepted

Does this imply finding the first $n$ primes has a polynomial time complexity?

In computational complexity theory, whenever you ask whether something runs in polynomial time, you need to clarify what quantity the runtime is a polynomial of. The most common definition of “...
user avatar
1 vote

Resources for a simple introduction to computational complexity

I would recommend Sipser's Theory of Computation text. It's reasonably close to a Math textbook and has excellent exposition. NP-completeness is a very standard topic, and you should be able to find ...
user avatar
  • 13.9k
1 vote

Computational power of superluminal signaling TM

It would probably be able to compute the same thing as a classical Turing Machine (the same laws apply to the atomic steps of computation) but everything can be computed in constant time as FTL ...
user avatar
  • 10k
1 vote
Accepted

Solving recurrence relation T(n/2) + n substitution method

$T(n)=O(\log(n))$ is not a statement about any particular $n$, but how the function $T(n)$ grows in the long term. The condition $c\ge n$ forces $c$ grows with $n$, therefore it goes to infinity as $n$...
user avatar
  • 7,410
1 vote
Accepted

time complexity and big O notation of sub set dynamic programming

The standard algorithm with time $O(nT)$ isn't exponential in terms of $T$, it's exponential in terms of input length, as instance with input $T$ (and $n$ numbers $\leq T$ each) has length $O(n\log T)$...
user avatar
  • 8,326
1 vote
Accepted

Is it possible to have two $NP$- complete languages whose union is $\{ 0, 1\}^*$?

The example from the question linked in comments is almost answer to your question. Let $S$ be any NP-complete language in alphabet $\{0, 1\}$. Let $L = \{\lambda\} \cup 1S \cup 0\{0, 1\}^*$ (either ...
user avatar
  • 8,326
1 vote

Solving recurrence T(n) = T(n - 1) + n^2 using substitution method.

To solve the recurrence exactly, you need to assume a more general ansatz: $$T(n) = An^3+Bn^2+Cn.$$ Substitution yields: $$An^3+Bn^2+Cn = A(n-1)^3+B(n-1)^2+C(n-1) + n^2.$$ If we let $n = 1,2,3$, we ...
user avatar
  • 421
1 vote
Accepted

Justifying that ISOLATED problem belongs to SPACE(log n)

Recall the Undirected Graph Connectivity Problem. Instance: An undirected graph $G(V, E)$, and vertices $u, v \in V(G)$. Decision: Is there a $u-v$ path in $G$? This problem is $\textsf{L}$-complete....
user avatar
  • 13.9k
1 vote

Computational cost/complexity of algorithms based on the number of mathematical operations

You are correct when you say that these are equivalent in the big-O sense. Each runs in time proportional to the input size $n$. Assuming that the cost of those arithmetic operations is the same (...
user avatar
1 vote

Oracle for solving super-exponential problems?

Let $A$ be $\textsf{PSPACE}$-complete. Then $\textsf{NP}^{A} \subseteq \textsf{PSPACE} \subseteq \textsf{P}^{A}$. The containment $\textsf{NP}^{A} \subseteq \textsf{PSPACE}$ follows from the following ...
user avatar
  • 13.9k

Only top scored, non community-wiki answers of a minimum length are eligible