 Replacement Part for Zoom H4N: Record Button
 Orbital reentry glider with no heat shield
 How can I use shadow from environment world (HDRI)?
 Importing OBJ to export STL for Sketchup
 How do you turn on constant interpolation for keyframes in blender?
 Using python and bmesh to scale/resize a face in place
 Blender stopped rendering with path tracing
 UV map not straight
 Eevee shadow problem
 Textures of toon shaded models?
 Cycles Principled BSDF paper material
 Boid Particle System Collison Objects
 How to make a procedural node setup to for raindrop effect for EEVEE?
 How do I resolve connection issues between two 10/100BaseTx to 100BaseFx fast Ethernet converters
 maldoc obfuscation
 Find out string encoding/shift of proprietary binary file format
 What is the name of the words group in English which translates into Russian in many words combination?
 What is the meaning of “disquieting suggestion”?
 What does “let’s get rocks” mean?
 What does “Agent Mulder's latest 302” mean?
NPComplete problems that admit an efficient algorithm under the promise of a unique solution
I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution. Thus showing that SAT does not admit an efficient algorithm even under the promise of there being at most one solution.
Through a parsimonious reduction (a reduction that preserves the number of solutions), it is easy to see that most NPcomplete problems (I could think of) also do not admit an efficient algorithm even under the promise of there being at most one solution (unless $\mathbf{NP = RP}$). Examples would be VERTEXCOVER, 3SAT, MAXCUT, 3DMATCHING.
Hence I was wondering if there was any NPcomplete problem that was known to admit a polytime algorithm under a uniqueness promise.
No NPcomplete problem is known to admit a polynomialtime algorithm under uniqueness promise. Valiant and Vazirani theorem applies t

No NPcomplete problem is known to admit a polynomialtime algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NPcomplete problem.
For all known NPcomplete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).
20180620 21:32:15