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 ...
- 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 ...
- 57.4k
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 ...
- 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 $...
- 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 ...
- 274
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 “...
- 8,895
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 ...
- 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 ...
- 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$...
- 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)$...
- 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 ...
- 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 ...
- 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....
- 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 (...
- 81k
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 ...
- 13.9k
Only top scored, non community-wiki answers of a minimum length are eligible