Tag Info

New answers tagged

2

Maybe I miss something, but it looks obvious that if $k<=n$ then you can rearrange the objects in the simplest way. Number the objects of each bin from 0 to k-1 and move object i to the i'th next bin. Before: bin A: {A0, A1, A2} bin B: {B0, B1, B2} bin C: {C0, C1, C2} bin D: {D0, D1, D2} After: bin A: {A0, D1, C2} bin B: {B0, A1, D2} bin C: {C0, B1, ...


2

Question 1: No counterexample: bin 1 = $[1,2,3]$, bin 2 = $[4,5,6]$


11

If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see ...


14

The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in: Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421 (1979) From the paper: ... 4. Some #P-complete problems ... 14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected) Input: $G; s,t ...


1

research on graph isomorphism has generally gone in the direction of looking at efficient or improved algorithms for many special graph classes with P-Time algorithms for which there has been much progress, and also more empirical analysis with state-of-the-art software eg Nauty looking somewhat at average and worst case behaviors separately. for the general ...


1

The problem is at least NP-hard, by a reduction from 3-SAT. First consider the problem of finding a path from the Start to the Exit of the following directed graph with the restriction that no path may visit all three (square) nodes of a clause: For this graph, such a path only exists if the formula $(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$ can ...


5

It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-812.. I have not read this paper, but I hope that this answer will help you in some extent.



Top 50 recent answers are included