[1] [1] [1] [cor1]Corresponding author [fn1]These authors contributed equally
to this work. 1]organization=Electrical, Computer, and Systems Engineering
Department, Rensselaer Polytechnic Institute, addressline=110 8th street,
city=Troy, postcode=12180, state=NY, country=USA 2] organization=Department of
Physics, Applied Physics and Astronomy, Rensselaer Polytechnic Institute,
addressline=110 8th street, city=Troy, postcode=12180, state=NY, country=USA

# Femtosecond Filament Coupled with Structured Light for Free Space Optical
Communication

Saad Bin Ali Reza Tianhong Wang Finn Buldt Pascal Bassène<EMAIL_ADDRESS>[  [
Moussa N’Gom

###### Abstract

The generation of a laser filament through clouds produces a shockwave which
displaces the small water droplets from the air to create a quasi-transparent
channel through which, information can be transmitted. We present a robust
method that utilizes the channel for free-space optical communication using
structured light beams coupled with a femtosecond filament. Vortex beams based
on their spatial profiles and non-diffractive characteristics are perfectly
suited to propagate around the filament. We have also developed a 4-bit
communication channel using these structured light beam. We introduce a method
dubbed segmented space division multiplexing. Our system demonstrates
resilience to noise and is unaffected by the filament. This method can improve
the scalability, robustness, and capacity of the free optical channel.

###### keywords:

Free space optical communication Filamentation Orbital angular momentum

##  1 Introduction

Light based communication between orbiting satellites and Earth’s surface
offers the prospect of significantly increasing space to ground data rates and
constitutes a key element in future for secure worldwide quantum communication
networks[1, 2, 3]. Free space optical links between Earth and space referred
to as Free Space Optical Communication (FSO) faces a persistent nemesis in the
form of atmospheric clouds. The randomness in size and position of water
droplets, which make up a rain cloud leads to substantial scattering of the
optical energy and quickly scramble the signal encoded in thin laser beams.
The amplitude fluctuation and wave-front distortion caused by atmospheric
turbulence can additionally severely degrade the coupling efficiency and
increase the bit-error-rate. This barrier is currently surmounted by
increasing the number of networked ground station, a very complex and
expensive solution.
Early attempts to clear the sky from fog and clouds with high power CW CO2
laser mainly for increasing visibility have been realized. However, a very
high energy is required to vaporize and shatter water drops (typically 10
kW.cm2 and 10$-$1000 MW.cm2 by pulse [4, 5]). Other methods use an aperture
averaging technique to attenuate the amplitude fluctuation utilizing adaptive
optics (AO) methods to compensate for the wave-front distortion caused by
atmospheric turbulence [6, 7]. The emergence of femtosecond (fs) terawatt
class lasers is an opportunity to reconsider FSO through dense clouds or fog
with a fundamentally different approach: nonlinear propagation in the
atmosphere and laser filamentation [2, 8, 9]. Compared to radio frequency (RF)
communication, FSO operates at higher frequencies with wide-open bandwidth,
resulting in significantly higher capacity communication links. One promising
scheme to tackle signal losses in FSO, is to couple a laser filament together
with a light beam carrying the signal. The filament displaces water droplets
in its immediate vicinity to create a quasi-transparent channel within which
the signal beam can travel unobstructed [9].
Filamentation is a phenomenon describing a long thin plasma channel (the
filament), produced by the balance between the optical Kerr effect and plasma
defocusing [10, 11, 12, 13, 14, 15]. Laser filaments are self-sustained light
of typically dozen micrometers diameter and up to hundreds of meters in
length, widely extending the traditional linear diffraction limit [16, 17, 18,
19, 20]. Properties of filaments such as their stability under air turbulence
[21, 22] and their interaction with water droplets have been studied [23].
The creation of the filament is accompanied by an expanding shock-wave that
creates a cylindrical quasi-transparent channel around the filament [9, 24].
Schimmel, et al. used a high repetition rate laser to demonstrate that the
cleared channel can become a stable millimeter-sized waveguide virtually clear
of obstructions [9].
Gaussian beams, coupled to a filament have been used as signal carriers [9].
However, the Gaussian signal can be affected by the filament. The dispersive
effects of the filament can cause the information signal to be degraded. This,
in addition to scattering from the remaining water droplets, are a serious
barrier for the implementation of this method.

Here, we propose to embed the filament within a donut shaped light beam that
can be used as the information carrier. The signal carrying light are
structured light with non-diffractive properties that we generate dynamically
using a spatial light modulator (SLM). The SLM allows us to create and control
higher order Laguerre-Gauss (LG) and Bessel-Gauss (BG) beams, which are
annular vortex beams possessing orbital angular momentum (OAM). Unlike
Gaussian beams, the transverse intensity profile of these vortex beams have
minimal diffraction as they propagates over a finite distance. The SLM further
allows us to control the diameter of the annular beam to fit within the
cleared channel. We then demonstrate a 4-bit Segmented Space Division
Multiplexing (SSDM) scheme using a higher order LG beam. The principle behind
the SSDM technique is to spatially divide the annular beam into segments,
which can be modulated individually. Each segment of the donut shaped beam is
generated using its own modified holographic mask.

##  2 Experimental Setup

An illustration of our experimental setup is shown in Figure 1. The
femtosecond laser is a Coherent Legend Elite Duo with center wavelength at
$\lambda$ = 810 nm. Its repetition rate is operated at 3 kHz with a measured
pulse width of 52 fs, with pulse energy at 1.67 mJ.

Figure 1: Schematic of the experimental setup. L: lens $f=2$ m, BE: beam
expander, SLM: spatial light modulator, I: Iris, DM: dichroic mirror, IF:
interference filters, ND: neutral density filters, MC: mirror coupler.
Structured light beam generated by the SLM is coupled with the filament
through the MC. After filtering out the femtosecond pulse with a DM, IF, and
ND, the structured light is imaged by an sCMOS camera. Inset (a): Side view
picture of the filament (glowing line) in air with a yellow line as a guide.
Inset (b): Image of the in-house developed MC.

The femtosecond beam is focused through air by a 2 m focal length anti-
reflection (AR) coated lens. The side view of the resulting filament is imaged
using a Sony $\alpha$ a5000 camera and is shown in Figure 1$-$(a), where the
white glowing line is the filament. A ruler is placed behind the filament as a
reference.
The light carrying signal is a continuous wave (CW), single longitudinal mode
diode laser with wavelength $\lambda$ = 635 nm. The signal beam is collimated
and expanded using a beam expander (BE1). The diameter of the beam is chosen
so that it covers the entire face of the SLM. The light modulator is a Santec
SLM-200 phase-only SLM.
We display various holographic masks on the SLM to generate any desired
structured light beams [25]. An iris (I) is used to block out the undesired
part of the signal. The remaining light is expanded and collimated using a
second beam expander BE2 before the designed mirror coupler (MC). The in-house
developed MC is pictured in Figure 1–(b). It is a 2" (50.8 mm) gold mirror in
which, we have drilled a hole approximately 6.3 mm in diameter.
The MC is placed at the focal point of lens (L) so that the entire femtosecond
beam passes through the hole. The advantage of using a MC as opposed to a
traditional beam combiner is that the femtosecond beam in its entirety is
utilized to produce the filament. In general this will always result in a
filament with higher plasma density [26]. A combination of dichroic mirror
(DM), interference filters (IF), and neutral density filters (ND) are placed
before the detectors to reduce the intensity of the femtosecond beam. The
coupled lasers are imaged using a Thorlabs sCMOS camera.

##  3 Results and Discussion

The filaments we produce are a little less than a meter in length, limited by
the lab environment. The critical power ($\mathcal{P}_{cr}$) for filamentation
to occur is governed by [15]:

$\mathcal{P}_{cr}=\frac{\lambda}{8\pi Cn_{0}n_{2}}$ (1)

where $\lambda$ is the wavelength of the laser, $C$ is the numerical factor
defined by the beam profile, $n_{0}$ is the refractive index of the medium
(air), and $n_{2}$ is the nonlinear refractive index due to the optical Kerr
effect.
Once we produce the desired length filament, we proceed to embed in the
different vortex beam different beams; eg. LG and BG beams. We also discuss
the possibility of using an array of Gaussian beams and zeroth order BG beam
to discuss the effect of the filament on Gaussian like beams.

###  3.1 LG Beam and Segmented Space Division Multiplexing

The phase singularity at the center of a vortex beam along its propagation
axis, ensures no light is directly interacting with the filament. Also, the
spatial profile and the immunity to diffractive spreading should allow it to
effectively work in the quasi-transparent channel cleared by a filament. We
produce a Laguerre-Gauss (LG) beam by illuminating the SLM which is displaying
the corresponding phase mask [25].

Figure 2: (a) The femtosecond beam after the filament and filtering. (b) The
LG ($\ell=12$) beam. (c) The coupled beams. (d) Segmented space division
multiplexing mechanism. The ring is divided into 4 quadrants representing 4
bits. Each quadrant is controlled separately by the SLM.

The inner diameter of the LG beam is related to its topological charge
($\ell$) and the beam waist ($w\sim 1$ cm) by $w\sqrt{2\ell}$. To correctly
reflect the donut beam, the minimum ratio between the inner diameter of the LG
beam and the diameter of the hole in the in-house developed MC (Figures
1$-$(b)) equals 7. We use an LG beam with $\ell=12$ which does not interact
with the filament.
Figure 2 depicts how the filament is embedded into the LG beam. The
femtosecond beam shown in Figure 2–(a), is attenuated by several orders of
magnitude after the filament to avoid damaging the detectors. The LG signal
and the fully embedded filament are shown in Figures 2–(b) and 2–(c). We vary
the inner diameter of the annular beam between 7.6$-$10 mm, using beam
expender (BE2). This allows an extra flexibility to ensure that the annular
beam fits well within the cleared channel.
The basic principal of SSDM is to divide the LG beam into 4 quadrants, each
representing a bit. A visual representation of this is shown in Figure 2–(d).
Since the LG beam is fully controlled by the phase mask on the SLM, each
quadrant can be controlled individually by manipulating the phase mask [25].
The middle of each quadrant is selected as the detection zone to maximize the
efficiency of the scheme.
The SSDM signals (Figure 3(e)$-$3(h)) are produced by specific phase masks
displayed on the SLM screen. The phase masks (Figure 3(a)$-$3(d)) that
generate the segmented beams are modified versions of the LG phase mask.

Figure 3: Holographic masks displayed on the SLM to generate the intensity
profile of the segmented LG beams. In the top row (a–d) are shown the masks
used to generate respectively the donut LG beam (e) and the 1/4 (f), 2/4 (g),
and 3/4 (h) segmented LG beams.

A binary function is added on top of each super pixel or quadrant of the phase
mask such that a single LG beam is divided into four independent segments.
This enables the transmission of four multiplexed channels over one carrier.

Figure 4: Simulation of 4-segmented bits by modulating an LG beam. Here are
represented all the combinations of the 4-bit segmented system from 0000 (top
left) to 1111 (bottom right). Figure 5: The results of the Segmented space
division multiplexing experiment. (a)-(f): The multiplexed LG beams. Each of
these beams show a specific arrangement of bits. (g)-(l): Multiplexed beams
coupled with the filament.

The resulting beam has 16 possible combinations that are realized by
individually modulating the intensity of each segment. Therefore, no signal is
state 0000 and the full donut beam is the 1111 state as shown in Figure 4.
This results in a noise resilient FSO scheme, with a signal to noise ratio
(SNR) of 17.8 dB. The SNR was calculated using:

$\rm{SNR}=20\times\log_{10}\left(\frac{Signal}{Noise}\right)$ (2)

The signal and the noise are characterized using a power-meter set up at the
place of the sCMOS camera. The power meter is placed at the detection zones as
indicated in Figure 2–(d). The signal values are measured with parts of the LG
beam illuminating the power-meter together with the ultrafast signal. To
calibrate the noise, the LG beam is blocked and the pump is left on. For each
sets of measurements, the power from each signal is kept constant.
Various examples of the modulated beam can be seen in Figure 5. The left
column Figure 5$-$(a) through (f) shows just the modulated LG beam, whereas
the right column Figure 5$-$(g) through (l) shows the corresponding coupled
beams. It can be seen that this scheme produces a 4$-$bit multiplexed signal
with minimal crosstalk between bits and that the signal is unaffected by the
presence of the filament. In Figure 5 six combinations are represented as a
showcase rather than the full list of all the 16 combinations for the 4-bit
system. Furthermore, we demonstrate that each quadrant can be modulated
independently.

###  3.2 Gaussian array

Another structured light beam that can be coupled around the filament is the
Gaussian array. As shown in Figure 6$-$(a), 8 separated Gaussian beams are
arranged in a square, the center of which is left empty by design. The
Gaussian array can be arranged to form numerous shapes according to the
configuration of the phase mask.

Figure 6: (a): 8 Gaussian beam array generated using the SLM. (b): 8 Gaussian
beam array coupled with the filament.

Thus the Gaussian array provides a unique solution to create an information
channel that can be configured to closely match the spatial characteristics of
the quasi-transparent channel. Like LG beams, the Gaussian array can also be
used in a SSDM scheme. Each beam representing a bit can be individually
controlled via the SLM. In this way the Gaussian array can form an $n$–bit
SSDM communications system. Scalability of this system expands the potential
of FSO systems to work at much higher capacities than current solutions.
However, the Gaussian beams do not possess the non-diffractive characteristics
of the LG beam. Therefore, the probability of crosstalk between bits is
increased.

###  3.3 Bessel-Gaussian beams and interaction with filament

In order to demonstrate how the filament interacts with other light sources,
we replaced the SLM in Figure 1 with an axicon ($\alpha$ = 0.5∘) and the MC
with a DM. The resulting 0th order Bessel-Gaussian (BG) beam was expanded and
was coupled with the filament. Figure 7$-$(a) shows the BG beam while the
femtosecond beam is blocked. In figure 7.(b) the femtosecond beam is unblocked
and forms the filament through the Gaussian center of the BG beam. As shown in
the figure, the filament causes the center of the BG beam to diverge outwards.

Figure 7: (a): 0th order Bessel-Gaussian (BG) beam with the femtosecond beam
blocked. (b): BG coupled with the filament. The filament causes the light to
diverge from the center and hence we see a hole despite it being a 0th order
BG.

This interaction is not contained to the center of the BG beam, with the
effects visible in the 1st and to a lesser degree in the 2nd concentric rings.
This interaction introduces crosstalk between channels and is detrimental to
the overall performance of the system. Taking Figure 7 as an example, the SNR
drops from 15.6 dB in Figure 7$-$(a) to 9.4 dB in Figure 7$-$(b). Research
conducted previously demonstrated the self-reconstruction properties of BG
beams [28]. This is particularly useful when it comes to FSO as, partially
obstructing the beam will lead to self-reconstruction. However this is only
possible with higher order BG beams as the 0th order BG beam will inevitably
be affected by the filament.

##  4 Conclusion

We have experimentally demonstrated a novel and robust scheme for FSO by
embedding a femtosecond laser filament within non-diffractive structured light
beams with donut shaped intensity distribution. We have devised a new method
to couple the signal carrying the information to the filament using an in-
house mirror coupler. We have also proposed a spaced division multiplexing
scheme that showed minimal crosstalk between channel while significantly
increasing the capacity of the data transmitted. We have coupled the filament
with beams possessing Gaussian-like distribution to show that the
implementation of this method will lead to crosstalk and interference with the
filament. We believe that the hybrid method of communication we have presented
will result in robust FSO communication systems, which can be implemented to
compensate for losses induced by difficult weather conditions.

Funding: This work is supported in part by the National Geospatial Intelligent
Agency grant $\\#$HM04762010012.

Disclosures: The authors declare no conflicts of interest.

## References

  * [1] A. G. Bell, On the production and reproduction of sound by light, American Journal of Science s3-20 (1880) 305–324.
  * [2] M. A. Khalighi and M. Uysal, Survey on Free Space Optical Communication: A Communication Theory Perspective, IEEE Communications Surveys Tutorials 16 (2014) 2231–2258.
  * [3] D. J. Israel, B. L. Edwards, and J. W. Staren, Laser Communications Relay Demonstration (LCRD) update and the path towards optical relay operations, in: 2017 IEEE Aerospace Conference, 2017, pp. 1–6.
  * [4] H. S. Kwok, T. M. Rossi, W. S. Lau, and D. T. Shaw, Enhanced transmission in CO2-laser–aerosol interactions, Optics Letters 13 (1988) 192–194.
  * [5] V. K. Pustovalov and I. A. Khorunzhii, Thermal and optical processes in shattering water aerosol droplets by intense optical radiation, Int. J. Heat Mass Transfer 35 (1992) 583–589.
  * [6] I. E. Lee, Z. Ghassemlooy, W. P. Ng, M. A. Khalighi, and S. K. Liaw, Effects of aperture averaging and beam width on a partially coherent Gaussian beam over free-space optical links with turbulence and pointing errors, Applied Optics 55 (2016) 1–9.
  * [7] N. Leonhard, R. Berlich, S. Minardi, A. Barth, S. Mauch, J. Mocci, M. Goy, M. Appelfelder, E. Beckert, and Claudia Reinlein, Real-time adaptive optics testbed to investigate point-ahead angle in pre-compensation of Earth-to-GEO optical communication, Optics Express 24 (2016) 13157–13172.
  * [8] J. Kasparian, M. Rodriguez, G. Méjean, J. Yu, E. Salmon, H. Wille, R. Bourayou, S. Frey, Y. B. Andre, A. Mysyrowicz, R. Sauerbrey, J. P. Wolf, and L. Woeste, White-Light Filaments for Atmospheric Analysis, Science 301 (2003) 61–64.
  * [9] G. Schimmel, T. Produit, D. Mongin, J. Kasparian, and J. -P. Wolf, Free space laser telecommunication through fog, Optica, 5 (2018) 1338–1341.
  * [10] P. L. Kelley, Self-focusing of optical beams, Phys. Rev. Lett. 15 (1965) 1005–1008.
  * [11] G. A. Askar’yan, The self-focusing effect, IOP Publishing 16 (1974) 680–686.
  * [12] A. Braun, G. Korn, X. Liu, D. Du, J. Squier, and G. Mourou, Self-channeling of high-peak-power femtosecond laser pulses in air, Opt. Lett. 20 (1995) 73–75.
  * [13] S. L. Chin, S. A. Hosseini, W. Liu, Q. Luo, F. Théberge, N. Aközbek, A. Becker, V. P. Kandidov, O. G. Kosareva, and H. Schroeder, The propagation of powerful femtosecond laser pulses in optical media: physics, applications, and new challenges, Canadian Journal of Physics 83 (2005) 863–905.
  * [14] S. L. Chin, T. -J. Wang, C. Marceau, J. Wu, J. S. Liu, O. Kosareva, N. Panov, Y. P. Chen, J. -F. Daigle, S. Yuan, A. Azarm, W. W. Liu, T. Seideman, H. P. Zeng, M. Richardson, R. Li, and Z. Z. Xu, Advances in intense femtosecond laser filamentation in air, Laser Physics 22 (2012) 1–53.
  * [15] A. Couairon and A. Mysyrowicz, Femtosecond filamentation in transparent media, Physics reports 441 (2007) 47–189.
  * [16] M. Durand, A. Houard, B. Prade, A. Mysyrowicz, A. Durécu, B. Moreau, D. Fleury, O. Vasseur, H. Borchert, K. Diener, R. Schmitt, F. Théberge, M. Chateauneuf, J. -F. Daigle, and J. Dubois, Kilometer range filamentation, Opt. Express 21 (2013) 26836–26845.
  * [17] P. Polynkin, M. Kolesik, A. Roberts, D. Faccio, P. D. Trapani, and J. Moloney, Generation of extended plasma channels in air using femtosecond bessel beams, Opt. Express 16 (2008) 15733–15740.
  * [18] M. Scheller, M. S. Mills, M. -A. Miri, W. Cheng, J. V. Moloney, M. Kolesik, P. Polynkin, and D. N. Christodoulides, Externally refuelled optical filaments, Nature Photonics 8 (2014) 297–301.
  * [19] M. Mills, M. Heinrich, M. Kolesik, and D. Christodoulides, Extending optical filaments using auxiliary dress beams, Journal of Physics B 48 (2015) 094014 .
  * [20] Z. Hong, Q. Zhang, S. A. Rezvani, P. Lan, P. Lu, Extending plasma channel of filamentation with a multi-focal-length beam, Opt. Express 24 (2016) 4029–4041.
  * [21] S. L. Chin, A. Talebpour, J. Yang, S. Petit, V. P. Kandidov, O. G. Kosareva, and M. P. Tamarov, Filamentation of femtosecond laser pulses in turbulent air, Applied Physics B 74 (2002) 67–76.
  * [22] A. Houard, M. Franco, B. Prade, A. Durécu, L. Lombard, P. Bourdon, O. Vasseur, B. Fleury, C. Robert, V. Michau, A. Couairon, and A. Mysyrowicz, Femtosecond filamentation in turbulent air, Phys. Rev. A 78 (2008) 033804.
  * [23] G. Méchain, G. Méjean, R. Ackermann, P. Rohwetter, Y. -B. André, J. Kasparian, B. Prade, K. Stelmaszczyk, J. Yu, E. Salmon, W. Winn, L. A. (Vern) Schlie, A. Mysyrowicz, R. Sauerbrey, L. Wöste, and J. -P. Wolf, Propagation of fs TW laser filaments in adverse atmospheric conditions, Applied Physics B 80 (2005) 785–789.
  * [24] B. Yan, H. Liu, C. Li, X. Jiang, X. Li, J. Hou, H. Zhang, W. Lin, B. Liu, and J. Liu, Laser-filamentation-assisted 1.25 gb/s video communication under harsh conditions, Optics & Laser Technology 131 (2020) 106391.
  * [25] V. Arrizón, U. Ruiz, R. Carrada, and L. A. González, Pixelated phase computer holograms for the accurate encoding of scalar complex fields, J. Opt. Soc. Am. A 24 (2007) 3500–3507.
  * [26] F. Théberge, W. Liu, P. T. Simard, A. Becker, and S. L. Chin, Plasma density inside a femtosecond laser filament in air: Strong dependence on external focusing, Phys. Rev. E 74 (2006) 036406.
  * [27] Y. Shen, Self-focusing: Experimental, Progress in Quantum Electronics 4 (1975) 1–34.
  * [28] S. Zhao, W. Zhang, L. Wang, W. Li, L. Gong, W. Cheng, H. Chen, and J. Gruska, Propagation and self-healing properties of bessel-gaussian beam carrying orbital angular momentum in an underwater environment, Scientific Reports 9 (2019) 1–8.


# A Critique of Du’s “A Polynomial-Time Algorithm for 3-”††thanks: Supported
in part by NSF grant CCF-2006496.

Yumeng He  Department of Computer Science
University of Rochester
Rochester, NY 14627, USA  Matan Kotler-Berkowitz  Department of Computer
Science
University of Rochester
Rochester, NY 14627, USA  Harry Liuson  Department of Computer Science
University of Rochester
Rochester, NY 14627, USA  Zeyu Nie  Department of Computer Science
University of Rochester
Rochester, NY 14627, USA

(April 5, 2024)

###### Abstract

In this paper, we examine the claims made by the paper “A polynomial-time
algorithm for 3-SAT” [Du10] by Lizhi Du. The paper claims to provide a
polynomial-time algorithm for solving the NP-complete problem 3-$\sat$. In
examining the paper’s argument, we find a flaw in one of the main sections of
its algorithm. We argue that this flaw causes the paper’s algorithm to
incorrectly decide that an infinite family of satisfiable 3-CNF boolean
formulas are not satisfiable. Therefore, the paper does not establish that
${\rm P}={\rm NP}$.

##  1 Introduction

This critique provides an analysis of Lizhi Du’s “A polynomial-time algorithm
for 3-$\sat$” [Du10]. The paper attempts to provide a polynomial-time
algorithm that decides whether a 3-CNF boolean formula is satisfiable. This
decision problem, known as 3-$\sat$, is a well-known NP-complete problem
[Kar72]. Therefore, Du claims that their algorithm can be used to solve any
problem in ${\rm NP}$, in polynomial time. This claim has significant
implications. Many widely-used algorithms have security claims that rely on
the assumption that ${\rm P}\neq{\rm NP}$, and many difficult problems may be
easily solvable if ${\rm P}={\rm NP}$. For instance, if Du’s claim is correct,
most forms of cryptography may be breakable [MM00], and problems such as
protein folding and finding mathematical proofs may become solvable in
polynomial time [BL98]. We thus explore the algorithm that Du provides [Du10].
We show that the algorithm incorrectly decides that certain satisfiable 3-CNF
boolean formulas are not satisfiable, which means that it is not a valid
algorithm for 3-$\sat$.

In Section 3, we present the relevant terminology from Du, and discuss how
Du’s algorithm purports to solve 3-$\sat$ in polynomial time. In particular,
in Section 3.2 we explain Du’s “Algorithm 1,” which purports to identify so-
called “indirect contradiction pairs”: pairs of literals in a 3-CNF boolean
formula for which no satisfying assignment exists that makes both literals
true. Next, in Section 4, we provide a counterexample that demonstrates how
Du’s Algorithm 1 incorrectly decides that certain satisfiable 3-CNF boolean
formulas are not satisfiable. Finally, we explain how this flaw means that
Du’s entire algorithm does not correctly decide 3-$\sat$, and thus Du’s claim
of ${\rm P}={\rm NP}$ does not follow from their arguments.

##  2 Preliminaries

In this paper, we assume basic familiarity with Turing machines and
computation, including the complexity classes ${\rm P}$ and ${\rm NP}$, and
NP-complete problems. A boolean formula is in conjunctive normal form (CNF) if
it is the conjunction of one or more clauses, where each clause is the
disjunction of zero or more literals. Each literal can be either $x$ or
$\bar{x}$ for any variable $x$. A boolean formula is in k-CNF form if each
clause of the formula has at most $k$ literals [Kar72]. For example, the
following is a 3-CNF boolean formula:

$(a\lor b\lor c)\land(d\lor\bar{b}).$

The 3-CNF satisfiability problem is defined as determining whether a given
3-CNF boolean formula is satisfiable (i.e., has an assignment to the variables
of the formula that makes the formula evaluate to true). The set 3-$\sat$
consists of all 3-CNF boolean formulas for which there exists a satisfying
assignment. 3-$\sat$ is NP-complete [Kar72]. Thus the existence of a
polynomial-time algorithm that decides 3-$\sat$ would imply ${\rm P}={\rm
NP}$.

##  3 Analysis

In this section, we introduce relevant terminology and algorithms from Du’s
paper.

Given a 3-CNF boolean formula, Du’s algorithm attempts to determine whether
there is a satisfying assignment for that formula. Let
$C_{i}=\\{u_{i_{1}},u_{i_{2}},u_{i_{3}}\\}$ refer to the $i$th clause of the
3-CNF formula, meaning that $C_{i}=u_{i_{1}}\lor u_{i_{2}}\lor u_{i_{3}}$. A
“unit” is simply a literal in the clause. We note, before we introduce the
following definitions, that Du’s use of the term “tree” seems to refer to the
way that the “tree” structure is constructed iteratively, with each “layer”
being added one at a time. In this context, a layer corresponds to a clause in
the original 3-$\sat$ instance, consisting of three or less “units”
(literals). Du’s “trees” have neither tree nor graph structure in the
conventional sense.

Given a 3-CNF boolean formula, Du’s algorithm transforms the formula into what
the paper calls a “standard checking tree” through iteratively adding new
clauses and deriving new “contradiction pairs.”

######  Definition 1 (Checking Tree).

A checking tree is a sequence of layers. A checking tree with $k+1$ layers
that are labeled $T_{0},\ldots,T_{k}$, is denoted as $T^{(k)}$. Since checking
trees are constructed iteratively, a checking tree may only have layers
corresponding to some of the clauses in the original 3-SAT instance.

######  Definition 2 (Long Path).

For a checking tree $T$ with $m$ layers, a long path is a list of literals
$P=(u_{1j_{1}},u_{2j_{2}},\ldots,u_{mj_{m}})$ such that $(\forall
k\in\\{1,2,\ldots,m\\})[u_{kj_{k}}\in T_{k}\wedge j_{k}\in\\{1,2,3\\}]$ and no
two literals in $P$ are negations of each other.

######  Definition 3 (Direct Contradiction Pair).

A direct contradiction pair is a pair of literals $\\{a,\bar{a}\\}$.

######  Definition 4 (Indirect Contradiction Pair).

For a checking tree $T$, an indirect contradiction pair is a pair of literals
$\\{a,b\\}$ such that there does not exist a long path $P$ of $T$ such that
both $a,b\in P$.

######  Definition 5 (Standard Checking Tree).

A standard checking tree is a pair $(T,C)$ where $T$ is a checking tree and
$C$ is the set of contradiction pairs of $T$. Contradiction pairs may be
either direct or indirect (Definitions 3 and 4).

In essence, a long path is a satisfying assignment of the partial 3-$\sat$
instance represented by $T$, with its clauses corresponding to the layers of
$T$. The goal of Du’s algorithm is to find a long path through the standard
checking tree that corresponds to the original 3-CNF formula.

The general process that Du gives to solve 3-$\sat$ is to iteratively
construct the standard checking tree by adding one layer at a time. After the
algorithm calculates all the contradiction pairs of $T^{(k)}$ for some natural
number $k\geq 1$, it adds a new layer corresponding to $C_{k+1}$ to form
$T^{(k+1)}$, and calculates the additional contradiction pairs of $T^{(k+1)}$.
The algorithm does this by using a destroyed checking tree, which we define
below.

###  3.1 Destroyed Checking Tree

######  Definition 6 (Destroyed Checking Tree).

A destroyed checking tree $D(T,S)$ of a standard checking tree $T$ and some
subset of literals $S$ is $T$ such that for all literals $s\in S$, if $s=x$
for some variable $x$, then, then all the occurences of $\bar{x}$ are removed
from $T$, and if $s=\bar{x}$ for some variable $x$, then all occurences of $x$
are removed from $T$. This corresponds to a modified problem with the
restriction that the literals in $S$ cannot be set to true.

Let $x,y$ be any pair of literals in the layers of $T^{(k)}$. To determine
whether $(x,y)$ is a new indirect contradiction pair, for all $v\in C_{k+1}$,
Du’s algorithm constructs a destroyed checking tree $D(T^{(k)},\\{x,y,v\\})$.
If for all such $v\in C_{k+1}$, the destroyed checking tree is unsatisfiable,
then $(x,y)$ must be a contradiction pair in $T^{(k+1)}$, as a long path
through $T^{(k+1)}$ must have a literal in the last layer, $C_{k+1}$.

This requires that we determine the satisfiability of the destroyed checking
tree. Du’s algorithm first “repairs” the destroyed checking tree to a standard
checking tree using Algorithm 1. When a destroyed checking tree is created, it
is comprised of the set of contradiction pairs from the standard checking tree
from which it was created. However, these contradiction pairs may no longer be
valid in the destroyed checking tree, as the destroyed literals impose
additional constraints on the possible solutions to the problem. As such, Du’s
paper uses Algorithm 1 to augment the set of contradiction pairs and “repair”
the checking tree to obtain an (ostensibly) updated, correct set of
contradiction pairs for the destroyed checking tree.

It then uses a somewhat convoluted procedure, Algorithm 2, which we will not
discuss in depth here, in order to determine satisfiability. We observe that
this procedure can actually be simplified, as given a standard checking tree
$T$ and a set of contradiction pairs $R$, $T$ is unsatisfiable if and only if
$R$ contains every pair of units in (some layers of) $T$. Then we can check
the satisfiability of the destroyed checking tree by invoking Algorithm 1.

###  3.2 Algorithm 1

Algorithm 1 takes a destroyed checking tree $D(T,S)$ as input. Let $\ell_{2}$
be the set of clauses with one or two literals, created as a result of
deleting literals. Let $\ell_{3}$ be the set of clauses with three literals.

For each unit $x$ that is a member of a clause in $\ell_{3}$, the algorithm
calculates its _useful units_ $U_{x}$ as the set of literals in clauses in
$\ell_{2}$ that are in a satisfying partial assignment of $\ell_{2}$
consistent with $x$. This is decidable in polynomial time, since 2-$\sat$
$\in$ P.

The issue arises in Step 3: “for each unit $u$’s each useful unit (sic), if in
another 3-unit layer, the units that do not destroy $u$ do not have this
useful unit, $u$ also has to lose this useful unit” [Du10].

“Destroy” here is not entirely clearly-defined. We interpret this as: For all
$(x,y)$ in distinct 3-unit layers that are not contradiction pairs of $T$, the
useful units of $x$ and $y$ are set as the intersection between the useful
units of $x$ and $y$. Section 4 demonstrates how Step 3 causes the algorithm
to incorrectly decide that certain 3-CNF formulas are unsatisfiable.

##  4 A Counterexample

Consider an instance of a standard checking tree, where $C_{1}\dots C_{n}$ are
some arbitrary clauses satisfying our assumptions below.

$\\\ s\lor t\lor\bar{c}\\\ C_{1}\\\ \vdots\\\ C_{n}\\\ \bar{s}\lor\bar{t}\lor
r.\\\ $ (1)

Now, suppose we are trying to add the clause $a\lor b\lor c$ to the tree.

Assume the existence of some unit $\alpha$ such that $(a,\alpha)$ and
$(b,\alpha)$ are contradiction pairs. Additionally suppose that all long paths
contain $c,\alpha$, and that $(s,\bar{t})$ and $(t,\bar{s})$ are not
contradiction pairs, and suppose that there exists at least one long path.

Then to check if $c,\alpha$ are a contradiction pair, we delete $\bar{c}$ and
$\bar{\alpha}$ from the tree. The resulting destroyed checking tree has the
form:

$\\\ s\lor t\\\ C^{\prime}_{1}\\\ \vdots\\\ C^{\prime}_{n}\\\
\bar{s}\lor\bar{t}\lor r.\\\ $ (2)

If $(s,\bar{t})$ and $(t,\bar{s})$ are not contradiction pairs, and $\alpha$
is in all long paths, then there must be some long path which has both
$\alpha$ and $\bar{s}$ and another one which has both $\alpha$ and $\bar{t}$.
Therefore $(\alpha,\bar{s})$ and $(\alpha,\bar{t})$ are not indirect
contradiction pairs. That is, they do not destroy each other. Clearly, $t$ is
$\bar{s}$’s only useful unit and $s$ is $\bar{t}$’s only useful unit. Then
Step 3 of Algorithm 1 causes $s$ and $t$ to be removed from $\alpha$’s useful
units. This causes $\alpha$ to be deleted in Step 7 since it has a layer with
zero useful units.

By our assumption that all valid long paths must contain $\alpha$, the
algorithm then concludes that there are no solutions and that $(c,\alpha)$
must be a contradiction pair.

This demonstrates one failure case of Algorithm 1. It can incorrectly conclude
that a destroyed checking tree has no solutions, leading to pairs incorrectly
being designated as indirect contradiction pairs. It is clear that incorrectly
labeling contradiction pairs may lead to the algorithm failing to output the
correct answer. For example, in the above case, if there was a single unique
solution requiring $c$ and $\alpha$ to be assigned true, then the algorithm
would fail.

Additionally, the clauses $C_{1},\ldots,C_{2}$ may be composed of any
arbitrary literals that satisfy our assumptions. Therefore, there is an
infinite family of 3-$\sat$ instances that Du’s algorithm decides incorrectly.

##  5 Conclusion

Du presents a complex algorithm that claims to decide in polynomial time
whether a 3-$\sat$ instance is satisfiable. Du’s algorithm is presented in
multiple parts, with each part relying on the output of the previous part. The
only part of Du’s paper that does not rely on another algorithm is Algorithm
1. If we assume that Algorithm 1 works correctly, the rest of Du’s algorithm
may indeed be able to decide 3-$\sat$ in polynomial time. However, as
demonstrated above, Algorithm 1 does not work correctly: There are satisfiable
instances of 3-$\sat$ that Algorithm 1 will identify as being unsatisfiable.
Since the entirety of Du’s algorithm relies on Algorithm 1, this flaw in
Algorithm 1 is fatal to the rest of Du’s algorithm. Thus Du’s paper has not
provided an algorithm that correctly decides an NP-complete problem in
polynomial time. As a result, the claim that ${\rm P}={\rm NP}$ does not
follow from the paper’s argument.

#### Acknowledgments

We would like to thank Michael C. Chavrimootoo, Lane A. Hemaspaandra, Michael
P. Reidy, and Eliot J. Smith for their helpful comments on prior drafts. The
authors are responsible for any remaining errors.

## References

  * [BL98] B. Berger and T. Leighton.  Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.  Journal of Computational Biology, 5(1):27–40, 1998.
  * [Du10] L. Du.  A polynomial time algorithm for 3-SAT.  Technical Report arXiv:1004.3702 [cs.CC], Computing Research Repository, arXiv.org/corr/, April 2010.  Revised October, 2023.
  * [Kar72] R. Karp.  Reducibilities among combinatorial problems.  In Complexity of Computer Computations, pages 85–103, 1972.
  * [MM00] F. Massacci and L. Marraro.  Logical cryptanalysis as a SAT problem.  Journal of Automated Reasoning, 24:165–203, 2000.