Proof of Nondeterministic Polynomial-Time Complete Problem for Soil Slope-Stability Evaluation
Publication: International Journal of Geomechanics
Volume 16, Issue 5
Abstract
Generally, slope-stability evaluation involves two coupled tasks: locating the critical slip surface and calculating its corresponding factor of safety. Various assessment methods have emerged in the past few decades, and the question of whether equivalence exists between these methods has become a controversial issue. Unfortunately, research that explores the roots of the slope-stability problem from the perspective of computational complexity is quite limited. This paper addresses this long-neglected but very important problem by rigorously proving that the evaluation of slope stability is essentially a nondeterministic polynomial-time complete problem, which is computationally one of the most difficult types of problems. A significant achievement of this proof is the inference that equivalence between the limit equilibrium method and the strength reduction method does not exist. The methods used throughout these routine analyses are exactly approximate and will not replace one another completely. The case study verified the aforementioned conclusions.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The research work presented here and the preparation of this paper have been financially supported by the National Basic Research Program of China (973 Program; Grant No. 2011CB710606), the China State Scholarship Fund (File No. 201208420293), the National Natural Science Foundation of China (NSFC; Grant Nos. 41102195 and 41572279), China Postdoctoral Science Foundation (Grant Nos. 2012M521500 and 2014T70758), and Hubei Provincial Natural Science Foundation of China (Grant No. 2014CFB901). This paper was significantly improved with the help of the anonymous reviewers. All support is gratefully acknowledged.
References
Abramson, L. W., Lee, T. M., Sharma, S., and Boyce, G. M. (2002). Slope stability and stabilization methods, 2nd Ed., John Wiley & Sons, New York.
Ahmed, A., Ugai, K., and Yang, Q. Q. (2012). “Assessment of 3D slope stability analysis methods based on 3D simplified Janbu and Hovland methods.” Int. J. Geomech., 81–89.
Amarasiri, A., and Kodikara, J. (2011). “Use of material interfaces in DEM to simulate soil fracture propagation in mode I cracking.” Int. J. Geomech, 314–322.
Bertrand, D., Nicot, F., Gotteland, P., and Lambert, S. (2008). “Discrete element method (DEM) numerical modeling of double-twisted hexagonal mesh.” Can. Geotech. J., 45(8), 1104–1117.
Bishop, A. W. (1955). “The use of the slip circle in the stability analysis of slopes.” Géotechnique, 5(1), 7–17.
Cai, F., and Ugai, K. (2004). “Numerical analysis of rainfall effects on slope stability.” Int. J. Geomech., 69–78.
Chakraborty, R., and Ghosh, A. (2013). “Three-dimensional analysis of contaminant migration through saturated homogeneous soil media using FDM.” Int. J. Geomech., 699–712.
Chen, W. F. (1975). Limit analysis and soil plasticity, Elsevier, Amsterdam, the Netherlands.
Chen, Z. Y. (2003). Stability analysis of soil slopes, China Water Power Press, Bejing, China.
Cheng, Y. M. (2007). “Global optimization analysis of slope stability by simulated annealing with dynamic bounds and Dirac function.” Eng. Optimiz., 39(1), 17–32.
Cheng, Y. M., Lansivaara, T., and Wei, W. B. (2007). “Two-dimensional slope stability analysis by limit equilibrium and strength reduction methods.” Comput. Geotech., 34(3), 137–150.
Cheng, Y. M., Lansivaara, T., and Wei, W. B. (2008). “Two-dimensional slope stability analysis by limit equilibrium and strength reduction methods: Reply.” Comput. Geotech., 35(2), 309–311.
Cheng, Y. M., and Lau, C. K. (2008). Slope stability analysis and stabilization: New methods and insight, Routledge, Abingdon, Oxon, U.K.
Clough, R. W., and Woodward, R. J. (1967). “Analysis of embankment stress and deformations.” J. Soil Mech. Found. Div., 93(4), 529–549.
Cook, S. (1992). “The P versus NP problem.” 〈http://www.claymath.org/sites/default/files/pvsnp.pdf〉 (Aug 30, 2014).
Craig, R. F. (2004). Craig's soil mechanics, 7th Ed., Spon Press, London.
Donald, I. B., and Giam, P. S. K. (1992). “The ACADS slope stability programs review.” Proc., 6th Int. Symp. on Landslides, Vol. 3, D. H. Bell, ed., Elsevier, Amsterdam, the Netherlands, 1665–1670.
Duncan, J. M. (1996). “State of the art: Limit equilibrium and finite-element analysis of slopes.” J. Geotech. Geoenviron. Eng., 577–596.
Duncan, J. M., and Wright, S. G. (2005). Soil strength and slope stability, John Wiley & Sons, Hoboken, NJ.
Farias, M. M., and Naylor, D. J. (1998). “Safety analysis using finite elements.” Comput. Geotech., 22(2), 165–181.
FLAC3D [Computer software]. Version 3.0. Itasca Consulting Group, Inc., Minneapolis.
Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York.
Goldreich, O. (2008). Computational complexity: A conceptual perspective, Cambridge University Press, Cambridge, U.K.
Greco, V. R. (1996). “Efficient Monte Carlo technique for locating critical slip surface.” J. Geotech. Engrg., 517–525.
Griffiths, D. V. (1980). “Finite element analyses of walls, footings and slopes.” Ph.D. thesis, Univ. of Manchester, Manchester, U.K.
Griffiths, D. V., and Lane, P. A. (1999). “Slope stability analysis by finite elements.” Géotechnique, 49(3), 387–403.
Hamdhan, I. N., and Schweiger, H. F. (2013). “Finite element method-based analysis of an unsaturated soil slope subjected to rainfall infiltration.” Int. J. Geomech., 653–658.
Han, J., Bhandari, A., and Wang, F. (2012). “DEM analysis of stresses and deformations of geogrid-reinforced embankments over piles.” Int. J. Geomech., 340–350.
Huang, S. L., and Yamasaki, K. (1993). “Slope failure analysis using local minimum factor-of-safety approach.” J. Geotech. Eng., 1974–1987.
Isakov, A., and Moryachkov, Y. (2014). “Estimation of slope stability using two-parameter criterion of stability.” Int. J. Geomech., 06014004.
Janbu, N. (1968). “Slope stability computations.” Soil mechanics and foundation engineering report, Technical Univ. of Norway, Trondheim, Norway.
Kulhawy, F. H. (1969). “Finite element analysis of the behavior of embankments.” Ph.D. thesis, Univ. of California, Berkeley, CA.
Li, L., and Chu, X. (2011). “An improved particle swarm optimization algorithm with harmony strategy for the location of critical slip surface of slopes.” China Ocean Eng., 25(2), 357–364.
Li, E., Zhuang, X., Zheng, W., and Cai, Y. (2014). “Effect of graph generation on slope stability analysis based on graph theory.” J. Rock Mech. Geotech. Eng., 6(4), 380–386.
Li, Y. C., Chen, Y. M., Zhan, T. L., Ling, D. S., and Cleall, P. J. (2010). “An efficient approach for locating the critical slip surface in slope stability analyses using a real-coded genetic algorithm.” Can. Geotech. J., 47(7), 806–820.
Liu, F. T., and Zhao, J. D. (2013). “Limit Analysis of Slope Stability by Rigid Finite-Element Method and Linear Programming Considering Rotational Failure.” Int. J. Geomech., 827–839.
Liu, X. (2010). “Research on dynamic response of slope in Wenchuan earthquake area.” Ph.D. thesis, China Univ. of Geosciences, Wuhan, China.
Liu, X., Tang, H., Hu, X., Wang, L., Liao, S., and Zou, Z. (2012). “Formation mechanism and dynamic stability of Jingu high-speed and long-run-out landslide.” Chinese J. Rock Mech. Eng., 31(12), 2527–2537.
Liu, X., Tang, H. M., and Xiong, C. R. (2013). “Patterns, problems, and development trends of analysis methods for slope dynamic reliability.” Rock Soil Mech., 34(5), 1217–1234.
Luo, X. F., Cheng, T., Li, X., and Zhou, J. (2012). “Slope safety factor search strategy for multiple sample points for reliability analysis.” Eng. Geol., 129–130, 27–37.
Malkawi, A. I. H., Hassan, W. F., and Sarma, S. K. (2001a). “An efficient search method for finding the critical circular slip surface using the Monte Carlo technique.” Can. Geotech. J., 38(5), 1081–1089.
Malkawi, A. I. H., Hassan, W. F., and Sarma, S. K. (2001b). “Global search method for locating general slip surface using Monte Carlo techniques.” J. Geotech. Geoenviron. Eng., 688–698.
Markoff, J. (2009). “Prizes aside, the P-NP puzzler has consequences.” 〈http://www.nytimes.com/2009/10/08/science/Wpolynom.html〉 (Aug. 30, 2014).
Markoff, J. (2010). “Step 1: Post elusive proof. Step 2: Watch fireworks.” 〈http://www.nytimes.com/2010/08/17/science/17proof.html?_r=2〉 (Aug. 30, 2014).
Morgenstern, N. R., and Price, V. E. (1965). “The analysis of the stability of general slip surfaces.” Géotechnique, 15(1), 79–93.
Pasternack, S. C., and Gao, S. (1988). “Numerical-methods in the stability analysis of slopes.” Comput. Struct., 30(3), 573–579.
Revilla, J., and Castillo, E. (1977). “Calculus of variations applied to stability of slopes.” Géotechnique, 27(1), 1–11.
SLOPE/W 2007–GeoStudio Network Edition. [Computer software]. GEOSLOPE International Ltd., Calgary, AB, Canada.
Spencer, E. (1967). “A method of analysis of the stability of embankments assuming parallel inter-slice forces.” Géotechnique, 17(1), 11–26.
Steward, T., Sivakugan, N., Shukla, S. K., and Das, B. M. (2011). “Taylor's slope stability charts revisited.” Int. J. Geomech., 348–352.
Tan, D., and Sarma, S. K. (2008). “Finite element verification of an enhanced limit equilibrium method for slope analysis.” Géotechnique, 58(6), 481–487.
Tang, H. M., Zhang, Y. H., and Sun, Y. Z. (2007). “A study of equivalent deformability parameters in rock masses.” Earth Sci., 32(3), 389–396.
Woeginger, G. J. (2014). “The P-versus-NP page.” 〈http://www.win.tue.nl/∼gwoegi/P-versus-NP.htm〉 (Aug. 30, 2014).
Zheng, H., Sun, G. H., and Li, C. G. (2011). “Cauchy problem of three-dimensional critical slip surfaces of slopes.” Int. J. Numer. Anal. Methods Geomech., 35(4), 519–527.
Zheng, H., Tham, L. G., and Liu, D. F. (2006). “On two definitions of the factor of safety commonly used in the finite element slope stability analysis.” Comput. Geotech., 33(3), 188–195.
Zhu, D. Y. (2001). “A method for locating critical slip surfaces in slope stability analysis.” Can. Geotech. J., 38(2), 328–337.
Zhu, D. Y., Qian, Q. H., and Lee, C. F. (2001). “Active and passive critical slip fields for cohesionless soils and calculation of lateral earth pressures.” Géotechnique, 51(5), 407–423.
Zhu, H. X., and Randolph, M. F. (2010). “Large Deformation Finite-Element Analysis of Submarine Landslide Interaction with Embedded Pipelines.” Int. J. Geomech., 145–152.
Zienkiewicz, O. C., Humpheson, C., and Lewis, R. W. (1975). “Associated and non-associated visco-plasticity and plasticity in soil mechanics.” Géotechnique, 25(4), 671–689.
Zou, J. Z., Williams, D. J., and Xiong, W. L. (1995). “Search for critical slip surfaces based on finite element method.” Can. Geotech. J., 32(2), 233–246.
Information & Authors
Information
Published In
International Journal of Geomechanics
Volume 16 • Issue 5 • October 2016
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Nov 25, 2014
Accepted: Jul 29, 2015
Published online: Dec 16, 2015
Discussion open until: May 16, 2016
Published in print: Oct 1, 2016
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.