| 1. |
- Wu, Lu-Lu, et al.
(författare)
-
Witness of unsatisfiability for a random 3-satisfiability formula
- 2013
-
Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. - 1539-3755 .- 1550-2376. ; 87:5, s. 052807-
-
Tidskriftsartikel (refereegranskat)abstract
- The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density alpha exceeds a critical value alpha(s) approximate to 4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density alpha > 19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density alpha > cN(b) with b approximate to 0.59 and prefactor c approximate to 8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.
|
|
| 2. |
- Wu, Renbing, et al.
(författare)
-
Pt nanodendrites anchored on bamboo-shaped carbon nanofiber arrays as highly efficient electrocatalyst for oxygen reduction reaction
- 2013
-
Ingår i: International journal of hydrogen energy. - : Elsevier BV. - 0360-3199 .- 1879-3487. ; 38:36, s. 16677-16684
-
Tidskriftsartikel (refereegranskat)abstract
- In order to improve the Pt utilization and enhance their catalytic performance in fuel cells, a novel composite electrode composed of single-crystalline Pt nanodendrites and support constructed by bamboo-shaped carbon nanofiber arrays (CNFAs) on carbon paper, is reported. This electrode is designed by growing vertically CNFAs on carbon paper via plasma enhanced chemical vapor deposition, followed by the direct synthesis of Pt nanodendrites using a simple surfactant-free aqueous solution method. Electron microscopy studies reveal that the Pt nanodendrites are uniformly high dispersed and anchored on the surface of CNFAs. Electrochemical measurements demonstrate that the resultant electrode exhibits higher electrocatalytic activity and stability for oxygen reduction reaction than commercial Pt/C catalyst, suggesting its potential application in fuel cells.
|
|
| 3. |
|
|
