New answers tagged complexity-classes
0
After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.
1
A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1].
You can also prove yourself that this problem is NPC by a straightforward ...
1
We will show that $A_{TM}$ is complete for your class.
In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$.
First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$.
Now, if $A\in L$, we need to ...
1
This problem is known as maximum matching of a bipartite graph.
Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task).
And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$.
The answer of the original problem is exactly the maximum matching of the new graph.
For algorithms, the classical Hungarian ...
0
Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).
In case your TMs are only defined as acceptors (i.e., a word not in the language will not ...
-3
Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,[8] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse ...
1
If you want to categorize a problem in a way that makes it comparable to other problems, then you need to categorize it the same way as everyone else does.
If you are only interested in one particular problem, then you can analyze it any way you like. You might look at the worst case, or the average case, or you can analyze "typical" cases, whatever "...
4
Because average case requires a definition of "average". Specifically, average over what distribution of inputs?
Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing.
...
Top 50 recent answers are included
