## New answers tagged computational-complexity

4

I assume you mean "there always exist $\tau_i$ such that $s_i^{t_i}(\tau_i) = 1$ and $s_j^{t_j}(\tau_i) = 0$ for $i \neq j$", i.e. you want that no matter how the sequences are shifted, each sequence has at least one bit which is zero in the other shifted sequences, and that's the slot when it manages to send its packet in your application.
(What ...

1

I'll posit that perhaps asking for a taxonomy on quantum algorithms might be overly narrowing, and searching for elusive superpolynomial speedups might be white whales. In actuality quantum computation might offer opportunities that are somewhat orthogonal to anything conceivable classically.
As an example, I think of proposals for quantum money, such as by ...

9

Your setup doesn't provide any complexity restrictions on determining whether a formula is an axiom or not, beyond demanding that this is computable. Thus, you won't be able to limit the complexity of proof verification either.
Determining the axioms is going to be the only issue, though. Any reasonable proof system will make verifiying proofs a polynomial-...

Top 50 recent answers are included

#### Related Tags

computational-complexity × 1065co.combinatorics × 190

algorithms × 175

graph-theory × 164

computer-science × 104

nt.number-theory × 101

lo.logic × 100

computability-theory × 85

reference-request × 81

np × 61

linear-algebra × 42

gr.group-theory × 40

computational-number-theory × 36

ag.algebraic-geometry × 30

combinatorial-optimization × 28

polynomials × 26

oc.optimization-and-control × 26

pr.probability × 23

matrices × 23

graph-colorings × 21

discrete-geometry × 20

approximation-algorithms × 18

linear-programming × 17

computational-geometry × 17

na.numerical-analysis × 16